题意

兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。 S 长度不超过 10^5， T 长度不会超过 S。 S 中只包含小写字母， T中只包含小写字母和“?”

分析

真的没想到这种题还可以用fft来做。。。

我们可以定义两个长度均为n的字符串的距离为 ∑ni=1(s1[i]−s2[i])2

显然当且仅当两个字符串的距离为0时他们相等。

但现在多了？这个字符，我们就可以重新定义字符串距离为 ∑ni=1s2[i]∗(s1[i]−s2[i])2

展开后就变成了fft的形式，直接上即可。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<complex> #include<cmath> #define pi acos(-1) using namespace std; typedef complex<double> com; const int MAXN=300005; int N,rev[MAXN],a[MAXN],b[MAXN]; com c[MAXN],d[MAXN],e[MAXN],f[MAXN]; char s1[MAXN],s2[MAXN]; void fft(com *a,int f) { for (int i=0;i<N;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int i=1;i<N;i<<=1) { com wn(cos(pi/i),f*sin(pi/i)); for (int j=0;j<N;j+=i*2) { com w(1,0); for (int k=0;k<i;k++) { com u=a[j+k],v=w*a[j+k+i]; a[j+k]=u+v;a[j+k+i]=u-v; w*=wn; } } } if (f==-1) for (int i=0;i<N;i++) a[i]/=N; } int main() { scanf("%s",s1+1); scanf("%s",s2+1); int len1=strlen(s1+1),len2=strlen(s2+1),lg=0; for (int i=1;i<=len1;i++) a[i]=s1[i]-'a'+1; for (int i=1;i<=len2;i++) b[len2-i+1]=s2[i]=='?'?0:s2[i]-'a'+1; for (N=1;N<=len1*2;N*=2,lg++); for (int i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1)); int w=0; for (int i=1;i<=len2;i++) w+=b[i]*b[i]*b[i]; for (int i=1;i<=len1;i++) c[i]=a[i]*a[i];for (int i=1;i<=len2;i++) d[i]=b[i]; for (int i=1;i<=len1;i++) e[i]=a[i];for (int i=1;i<=len2;i++) f[i]=b[i]*b[i]*2; fft(c,1);fft(d,1);fft(e,1);fft(f,1); for (int i=0;i<N;i++) c[i]=c[i]*d[i],e[i]=e[i]*f[i]; fft(c,-1);fft(e,-1); for (int i=0;i<N;i++) a[i]=(int)(c[i].real()+0.1)-(int)(e[i].real()+0.1); int tot=0; for (int i=len2+1;i<=len1+1;i++) if (a[i]+w==0) tot++; cout<<tot<<endl; for (int i=len2+1;i<=len1+1;i++) if (a[i]+w==0) printf("%d\n",i-len2-1); return 0; }