题目大意
给你两个字符串，N,M |N|>|M|，经过转换之后，问你，连续的一段，能够匹配上的最大元素个数。
n <1e5
题目分析
题目求区间内匹配数最大。考虑区间有n^2个，暴力做显然会T，所以这里考虑，用FFT
将第二个串反置，这样我们相邻位置的匹配，可以转化为，对应位置的匹配
如下图：
此时我们发现，最大匹配数 就是 i+j的系数
因此，我们分别求R,S,P的匹配，三次FFT之后将系数加起来，求一个最大值即可
代码分析
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e6+50;
const double pi = acos(-1.0);
typedef long long ll;
struct Complex
{
double x,y;
Complex(double _x = 0,double _y=0)
{
x=_x; y=_y;
}
Complex operator +(const Complex &b) const
{
return Complex(x+b.x,y+b.y);
}
Complex operator -(const Complex &b) const
{
return Complex(x-b.x,y-b.y);
}
Complex operator * (const Complex&b) const
{
return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
}
}a[maxn],b[maxn];
int S,T,n,m,L,R[maxn],ans[maxn]; //S 表示A序列的长度 ,T表示B序列的长度
//n 表示 >=S+T 的2的幂次 L表示幂次 R数组是旋转数组，ans答案数组
ll F[maxn];
double f[maxn][3],g[maxn][3];// f,g数组是整数转化为实数的数组
char x[maxn],y[maxn];
void FFT(Complex a[],int opt)
{
for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);// 翻转数组
for(int k=1;k<n;k<<=1)
{
Complex wn = Complex(cos(pi/k),opt*sin(pi/k));
for(int i=0;i<n;i+=(k<<1))
{
Complex w = Complex(1,0);
for(int j=0;j<k;j++,w=w*wn)
{
Complex x = a[i+j],y = w*a[i+j+k];
a[i+j] = x+y;
a[i+j+k] = x-y;
}
}
}
}
void calc(int opt)
{
FFT(a,1);
FFT(b,1);
for(int i=0;i<=n;i++) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=0;i<=n;i++) F[i] = (ll) (a[i].x/n+0.5)*opt;
}
int main()
{
scanf("%d%d",&S,&T);
S--,T--;
scanf("%s%s",x,y);
for(int i=0;i<=S;i++)
{
if(x[i]=='R') f[i][0] = 1.0;
if(x[i]=='S') f[i][1] = 1.0;
if(x[i]=='P') f[i][2] = 1.0;
}
for(int i=0;i<=T;i++)
{
if(y[i]=='R') g[T-i][1] = 1.0;
if(y[i]=='S') g[T-i][2] = 1.0;
if(y[i]=='P') g[T-i][0] = 1.0;
}
// for(int i=0;i<=T;i++) scanf("%lf",&g[i]);
m=T+S; L=0;
for(n=1;n<=m;n<<=1) L++;
for(int i=0;i<n;i++) R[i] = (R[i>>1]>>1)|((i&1)<<(L-1));
for(int kase=0;kase<3;kase++)
{
for(int i=0;i<=n;i++)
{
a[i]= Complex(1.0*f[i][kase],0.0);
b[i]= Complex(1.0*g[i][kase],0.0);
}
calc(1);
for(int i=0;i<=S+T;i++) {
ans[i]+=F[i];
// printf("%lld ",F[i]);
}
// printf("\n");
}
int allans=0;
for(int i=T;i<=S+T;i++) allans= max(allans,ans[i]);
printf("%d\n",allans);
return 0;
}
/*
12 4
PPPRRRRRRRRR
RSSS
12 4
RRRRRRRRRSSS
RRRS
*/
