题目链接：https://vjudge.net/problem/Gym-101667H
题目大意：首先给你两个字符串，R代表石头，P代表布，S代表剪刀，第一个字符串代表第一个人每一次出的类型，第二个字符串代表第二个人每一次出的类型，问怎么控制第二个人开始的地方，能使得第二个人获胜的几率最大，然后输出最多获胜的局数。
具体思路：FFT，我们首先把第二个字符串每一个类型全部转换成他的对立面，比如说石头就转换成布，布就转换成剪刀，剪刀就转换成石头，然后我们就直接用第二个字符串去匹配就可以了。
匹配的时候，我们是将三个分着进行的，先求从每一个位置开始子串的最大匹配量，三个分别求好之后，我们就遍历一下每一个位置看一下那个位置的最大匹配量就可以了。
AC代码：
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<stdio.h>
using namespace std;
# define ll long long
const double PI = acos(-1.0);
const int maxn = 4e5+;
struct complex
{
double r,i;
complex(double _r = ,double _i = )
{
r = _r;
i = _i;
}
complex operator +(const complex &b)
{
return complex(r+b.r,i+b.i);
}
complex operator -(const complex &b)
{
return complex(r-b.r,i-b.i);
}
complex operator *(const complex &b)
{
return complex(r*b.r-i*b.i,r*b.i+i*b.r);
}
};
void change(complex y[],int len)
{
int i,j,k;
for(i = , j = len/; i < len-; i++)
{
if(i < j)
swap(y[i],y[j]);
k = len/;
while( j >= k)
{
j -= k;
k /= ;
}
if(j < k)
j += k;
}
}
void fft(complex y[],int len,int on)
{
change(y,len);
for(int h = ; h <= len; h <<= )
{
complex wn(cos(-on**PI/h),sin(-on**PI/h));
for(int j = ; j < len; j += h)
{
complex w(,);
for(int k = j; k < j+h/; k++)
{
complex u = y[k];
complex t = w*y[k+h/];
y[k] = u+t;
y[k+h/] = u-t;
w = w*wn;
}
}
}
if(on == -)
for(int i = ; i < len; i++)
y[i].r /= len;
}
complex x1[maxn],x2[maxn];
char str1[maxn],str2[maxn];
int sum[maxn],len,len1,len2,ans[maxn];
void cal(char tmp)
{
for(int i=; i<len1; i++)
{
x1[i]=complex(str1[i]==tmp,);
}
for(int i=len1; i<len; i++)
{
x1[i]=complex(,);
}
for(int i=; i<len2; i++)
{
x2[i]=complex(str2[len2-i-]==tmp,);//记得要将第二个字符串进行翻转。
}
for(int i=len2; i<len; i++)
{
x2[i]=complex(,);
}
fft(x1,len,);
fft(x2,len,);
for(int i=; i<len; i++)
{
x1[i]=x1[i]*x2[i];
}
fft(x1,len,-);
for(int i=; i<len; i++)
{
sum[i]=(int)(x1[i].r+0.5);
}
for(int i=; i<len; i++)
{
ans[i]+=sum[i];
}
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
scanf("%s",str1);
scanf("%s",str2);
len=;
len1=strlen(str1);
len2=strlen(str2);
while(len<len1*||len<len2*)
len<<=;
for(int i=; i<len1; i++)
{
if(str1[i]=='R')
{
str1[i]='P';
}
else if(str1[i]=='P')
{
str1[i]='S';
}
else if(str1[i]=='S')
{
str1[i]='R';
}
}
cal('P');
cal('S');
cal('R');
int maxx=;
for(int i=len2-; i<len1+len2-; i++)//注意起点是第二个字符串的长度对应的下标，也就是冷len2-1.
{
maxx=max(maxx,ans[i]);
}
printf("%d\n",maxx);
return ;
}