题意:给两个字符串s,t，包括S,R,P，你可以调整t的位置，求t串最多能赢多少次，遵循剪刀石头布的原则。
题解:首先的想法是将赢变成有多少个字符串是相同的，变成了字符串相互匹配的问题。注意到只有三个元素不妨单独来算。那S来举例，将s,t中所有的S换成1，其他的换成0，将s,t看成是多项式 就是求
m
a
x
∑
s
i
+
k
∗
t
i
max \sum s_{i+k}*t_{i}
max∑si+k∗ti为。我们知道多项式乘法
C
i
=
∑
j
=
0
i
a
j
∗
b
i
−
j
C_i=\sum_{j=0}^{i} a_j*b_{i-j}
Ci=∑j=0iaj∗bi−j不妨将t翻转，就可以得到答案。多项式乘法用FFT 就行
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const double pi=acos(-1);
struct cp{
double r,i;
cp(){}
cp(double x,double y){
r=x;i=y;
}
cp operator +(const cp &a) const {
return cp(r+a.r,i+a.i);
}
cp operator - (const cp &a) const{
return cp(r-a.r,i-a.i);
}
cp operator * (const cp &a)const {
return cp(r*a.r-i*a.i,r*a.i+i*a.r);
}
}a[N<<2],b[N<<2];
int R[N<<2];//反码
int n,m,len,L,Len;
int ans[N<<2];
char s[N<<2],t[N<<2];
inline void fft(cp *a,int len,int op){
for(int i=0;i<len;i++) {
if(i<R[i]) swap(a[ i ],a[ R[i] ]);
}
for(int i=2;i<=len;i<<=1){//
cp wn=cp(cos(2*pi/i), op*sin(2*pi/i));//单位复数根
for(int j=0;j<len;j+=i){
cp w=cp(1.0,0.0);
for(int k=j;k<j+(i/2);k++,w=w*wn){
cp u=a[k];
cp v=w*a[k+i/2];
a[k]=u+v;
a[k+i/2]=u-v;
}
}
}
if(op==-1) for(int i=0;i<len;i++) a[i].r/=len;
}
void calc(char op){
memset(a,NULL,sizeof a);
memset(b,NULL,sizeof b);
for(int i=0;i<Len;i++) a[i].r=(s[i]==op?1:0);
for(int i=0;i<Len;i++) b[i].r=(t[i]==op?1:0);
fft(a,Len,1);
fft(b,Len,1);
for(int i=0;i<Len;i++) a[i]=a[i]*b[i];
fft(a,Len,-1);
for(int i=0;i<Len;i++) ans[i]+=(int)(a[i].r+0.5);
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s);scanf("%s",t);
// cout<<s<<" "<<t<<endl;
for(int i=0;i<n;i++){
if(s[i]=='P') s[i]='S';
else if(s[i]=='R') s[i]='P';
else s[i]='R';
}
// cout<<t<<endl;
reverse(t,t+m);
len=n+m-1;L=0;
for(Len=1;Len<len;Len<<=1) L++;
for(int i=0;i<Len;i++) R[i]=(R[i>>1]>>1)|(i&1)<<(L-1);
//
calc('P');calc('R');calc('S');
int Ans=0;
for(int i=m-1;i<len;i++) {
Ans=max(Ans,ans[i]);
}
cout<<Ans<<endl;
return 0;
}
/*
12 3
RRRRRRRRRRRR
RSS
*/