原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-D.html
给定两个字符串，在根据给定的字符表转成相应的字符之后，问前一个串在后面一个串中匹配了多少次。
一个串在另一个串的某一个位置匹配，当且仅当从该位置起截取长度与那个串相同的一个子串，这个子串与那个串等价。
定义两个串等价，当且仅当这两个串的对应位置的 Ascll 码值相差不大于 1 。
任意一个串的长度 $\leq 250000$。
FFT 基础套路题。
为了偷懒，我们写 11 次 DFT 。
但是这样做 double 精度不大行，long double 要超时。
所以我们用 NTT 来搞定。
注意别爆 long long 。
关于 FFT 和套路介绍，下面这个链接所指向的博文有详细介绍。
https://www.cnblogs.com/zhouzhendong/p/Fast-Fourier-Transform.html
套路：
首先将第一个串翻转一下。
然后构造式子：
$f_i=\sum_{j=0}^{i} (S_i-T_j)^2((S_i-T_j)^2-1)$
展开之后 NTT 算出来就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1<<22,mod=998244353;
int a,b,n,d;
int S[N],T[N],R[N];
char S1[N],T1[N];
char s[27];
int Pow(int x,int y){
int ans=1;
for (;y;y>>=1,x=1LL*x*x%mod)
if (y&1)
ans=1LL*ans*x%mod;
return ans;
}
int w[N],A[N];
int A4[N],A3[N],A2[N],A1[N],A0[N];
int B4[N],B3[N],B2[N],B1[N],B0[N];
void FFT(int a[],int n){
for (int i=0;i<n;i++)
if (i<R[i])
swap(a[i],a[R[i]]);
for (int t=n>>1,d=1;d<n;d<<=1,t>>=1)
for (int i=0;i<n;i+=(d<<1))
for (int j=0;j<d;j++){
int tmp=1LL*w[t*j]*a[i+j+d]%mod;
a[i+j+d]=(a[i+j]-tmp)%mod;
a[i+j]=(a[i+j]+tmp)%mod;
}
}
vector <int> vec;
int main(){
scanf("%s%s%s",S1,T1,s);
a=strlen(S1),b=strlen(T1);
for (int i=0;i<a;i++)
S1[i]=s[S1[i]-‘a‘];
for (int i=0;i<b;i++)
T1[i]=s[T1[i]-‘a‘];
for (int i=0;i<a;i++)
S[a-i-1]=S1[i]-‘a‘+1;
for (int i=0;i<b;i++)
T[i]=T1[i]-‘a‘+1;
for (n=1,d=0;n<a+b;n<<=1,d++);
for (int i=0;i<n;i++)
R[i]=(R[i>>1]>>1)|((i&1)<<(d-1));
w[0]=1,w[1]=Pow(3,(mod-1)/n);
for (int i=2;i<n;i++)
w[i]=1LL*w[i-1]*w[1]%mod;
for (int i=0;i<n;i++){
A0[i]=i<a?1:0;
A1[i]=S[i];
A2[i]=S[i]*S[i];
A3[i]=S[i]*S[i]*S[i];
A4[i]=S[i]*S[i]*S[i]*S[i];
B0[i]=i<b?1:0;
B1[i]=T[i];
B2[i]=T[i]*T[i];
B3[i]=T[i]*T[i]*T[i];
B4[i]=T[i]*T[i]*T[i]*T[i];
}
FFT(A0,n),FFT(A1,n),FFT(A2,n),FFT(A3,n),FFT(A4,n);
FFT(B0,n),FFT(B1,n),FFT(B2,n),FFT(B3,n),FFT(B4,n);
for (int i=0;i<n;i++)
A[i]=(1LL*A4[i]*B0[i]%mod
-4LL*A3[i]*B1[i]%mod
+6LL*A2[i]*B2[i]%mod
-4LL*A1[i]*B3[i]%mod
+1LL*B4[i]*A0[i]%mod
-1LL*A2[i]*B0[i]%mod
+2LL*A1[i]*B1[i]%mod
-1LL*B2[i]*A0[i]%mod)%mod;
w[1]=Pow(w[1],mod-2);
for (int i=2;i<n;i++)
w[i]=1LL*w[i-1]*w[1]%mod;
FFT(A,n);
for (int i=0,inv=Pow(n,mod-2);i<n;i++)
A[i]=1LL*A[i]*inv%mod;
vec.clear();
for (int i=0;i<b-a+1;i++)
if (A[i+a-1]==0)
vec.push_back(i+1);
printf("%d\n",(int)(vec.size()));
for (int i=0;i<vec.size();i++)
printf("%d ",vec[i]);
return 0;
}
2018牛客网暑假ACM多校训练赛（第三场）D Encrypted String Matching 多项式 FFT
原文：https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-D.html