Rock Paper Scissors
题目链接：
Rock Paper Scissors
Gym – 101667H
题意
给你两个串，长度分别为n,m。每个串由三个字符组成’R’,‘P’,‘S’，分别代表着石头剪刀布，第一个串代表是机器出的，第二个串代表是你出的，现在，你已知了机器出的顺序，可以跳过任意个，但是一旦开始就必须进行到比赛结束，所以，问最多赢几盘？
数据范围：
1
<
m
<
n
<
1
e
5
1<m<n<1e5
1
<
m
<
n
<
1
e
5
思路
这题可以先转换一下，将现在的第二个串转化成能够打败的串，所以，这样就只需要进行模式匹配即可。
但是，我们现在已有的模式匹配算法莫过于经典的KMP，但是，这一系列算法只能求连续最长子串。无法忽略中间的一些字符。
那DP可不可以，也不行，当前的信息，无法将状态转移到下一个。
最后，看了大神的博客，FFT？！！！
豁然开朗，在求一段匹配时，与卷积的形式非常像。
C
k
=
∑
i
=
0
,
j
=
0
,
i
+
j
=
k
a
i
b
k
x
i
C_k = \sum_{i=0,j=0,i+j=k} a_ib_kx^i
C
k
=
i
=
0
,
j
=
0
,
i
+
j
=
k
∑
a
i
b
k
x
i
这一段匹配代表着
a
0
a_0
a
0
与
b
k
b_k
b
k
,
a
1
a_1
a
1
与
b
k
−
1
b_{k-1}
b
k
−
1
…的匹配，那么我们只需将第二个串反转一下，这样代表的就是两个串的匹配字母个数。
我们再用三个字母分别做一次匹配加起来即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<':'<<x<<" ";
const int maxn = 4e5+7;
typedef complex<double> C;
C wn(int n, int f) {
return C(cos(acos(-1.0) / n), f*sin((acos(-1.0)) / n));
}
C inv(int n) {
return C(1.0 / n, 0);
}
C as[maxn], bs[maxn], cs[maxn];
C ar[maxn], br[maxn], cr[maxn];
C ap[maxn], bp[maxn], cp[maxn];
int g[maxn];
void FFT(C *a, int n, int f) {
for (int i = 0; i < n; i++) if (i > g[i]) swap(a[i], a[g[i]]);
for (int i = 1; i < n; i <<= 1) {
C w = wn(i, f), x, y;
for (int j = 0; j < n; j += i + i) {
C e;
e = 1;
for (int k = 0; k < i; e = e * w, k++) {
x = a[j + k];
y = a[j + k + i] * e;
a[j + k] = x + y;
a[j + k + i] = x - y;
}
}
}
if (f == -1) {
C Inv = inv(n);
for (int i = 0; i < n; i++) a[i] = a[i] * Inv;
}
}
void conv(C *a, int n, C *b, int m, C *c) {
int k = 0, s = 2;
while ((1 << k) < max(n, m) + 1) k++, s <<= 1;
for (int i = 1; i < s; i++) g[i] = (g[i / 2] / 2) | ((i & 1) << k);
FFT(a, s, 1);
FFT(b, s, 1);
for (int i = 0; i < s; i++) c[i] = a[i] * b[i];
FFT(c, s, -1);
}
char str[maxn];
char ptr[maxn];
int main()
{
int len1,len2;
scanf("%d %d",&len1,&len2);
scanf("%s %s",str,ptr);
for (int i = 0;i < len2;i ++) {
if (ptr[i] == 'S') ptr[i] = 'P';
else if (ptr[i] == 'P') ptr[i] = 'R';
else if (ptr[i] == 'R') ptr[i] = 'S';
}
reverse(ptr,ptr+len2);
int n, m; n = len1,m = len2;
for (int i = 0; i < n; i++) as[i] = str[i]=='S'?1.0:0.0;
for (int i = 0; i < m; i++) bs[i] = ptr[i]=='S'?1.0:0.0;
conv(as, n, bs, m, cs);
for (int i = 0; i < n; i++) ap[i] = str[i]=='P'?1.0:0.0;
for (int i = 0; i < m; i++) bp[i] = ptr[i]=='P'?1.0:0.0;
conv(ap, n, bp, m, cp);
for (int i = 0; i < n; i++) ar[i] = str[i]=='R'?1.0:0.0;
for (int i = 0; i < m; i++) br[i] = ptr[i]=='R'?1.0:0.0;
conv(ar, n, br, m, cr);
int mx = -1;
for (int i = m-1; i < n+m-1; i++) {
mx = max(mx,(int)(cs[i].real()+0.5) + (int)(cp[i].real()+0.5) + (int)(cr[i].real()+0.5));
}
printf("%d\n",mx);
}