2216. 你猜是不是KMP
★★★☆ 输入文件：guess.in 输出文件：guess.out 简单对比
时间限制：1 s 内存限制：256 MB
【题目描述】
XX在玩两个串的游戏。首先,他拿出了两个字符串 S 和 T,XX想知道 T在 S 中出现了几次,分别在哪些位置出现。注意 T 中可能有“?”字符,这个字符可以匹配任何字符。
【输入格式】
两行两个字符串,分别代表 S 和 T
【输出格式】
第一行一个正整数 k,表示 T 在 S 中出现了几次。
接下来 k 行正整数,
分别代表 T 每次在 S 中出现的开始位置。按照从小到大
的顺序输出,S 下标从 0 开始。
【样例输入】
ababcadaca
a?a
【样例输出】
3
0
5
7
【提示】
对于 10%的数据, S 和 T 的长度不超过 100
对于另外 20%的数据,T 中无“?”
对于 100%的数据,S 长度不超过 10^5,T 长度不会超过 S。S 中只包含小写
字母,T 中只包含小写字母和“?”
【来源】
经典题目
这道题咩，是FFT哦，咳咳……
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 using namespace std; 6 const int maxn=400010; 7 const double PI=acos(-1.0); 8 char s[maxn],t[maxn]; 9 int a[maxn],b[maxn]; 10 struct complex{ 11 double r,i; 12 complex(double r_=0.0,double i_=0.0){ 13 r=r_;i=i_; 14 } 15 complex operator +(complex a){ 16 return complex(r+a.r,i+a.i); 17 } 18 complex operator -(complex a){ 19 return complex(r-a.r,i-a.i); 20 } 21 complex operator *(complex a){ 22 return complex(r*a.r-i*a.i,r*a.i+i*a.r); 23 } 24 }; 25 complex A[maxn],B[maxn],C[maxn],D[maxn],E[maxn]; 26 27 void Rader(complex *a,int len){ 28 int k; 29 for(int i=1,j=len>>1;i<len-1;i++){ 30 if(i<j)swap(a[i],a[j]); 31 k=len>>1; 32 while(j>=k){ 33 j-=k; 34 k>>=1; 35 } 36 j+=k; 37 } 38 } 39 40 void FFT(complex *a,int len,int on){ 41 Rader(a,len); 42 for(int h=2;h<=len;h<<=1){ 43 complex wn(cos(-on*PI*2.0/h),sin(-on*PI*2.0/h)); 44 for(int j=0;j<len;j+=h){ 45 complex w(1,0); 46 for(int k=j;k<j+(h>>1);k++){ 47 complex u=a[k]; 48 complex v=a[k+(h>>1)]*w; 49 a[k]=u+v; 50 a[k+(h>>1)]=u-v; 51 w=w*wn; 52 } 53 } 54 } 55 if(on==-1) 56 for(int i=0;i<len;i++) 57 a[i].r/=len; 58 } 59 int ans[maxn],tot; 60 int main(){ 61 freopen("guess.in","r",stdin); 62 freopen("guess.out","w",stdout); 63 scanf("%s%s",s,t); 64 int lens=strlen(s); 65 int lent=strlen(t); 66 for(int i=0;i<lens;i++) 67 a[i]=s[i]-'a'+1; 68 for(int i=0;i<lent;i++){ 69 if(t[i]=='?') 70 b[lent-i-1]=0; 71 else 72 b[lent-i-1]=t[i]-'a'+1; 73 } 74 75 int len=1; 76 while(len<=lens+lent)len<<=1; 77 78 for(int i=0;i<lens;i++)A[i]=complex(1.0,0); 79 for(int i=0;i<lent;i++)B[i]=complex(1.0*b[i]*b[i]*b[i],0); 80 FFT(A,len,1);FFT(B,len,1); 81 for(int i=0;i<len;i++)C[i]=A[i]*B[i]; 82 FFT(C,len,-1); 83 84 memset(A,0,sizeof(A)); 85 memset(B,0,sizeof(B)); 86 for(int i=0;i<lens;i++)A[i]=complex(2.0*a[i],0); 87 for(int i=0;i<lent;i++)B[i]=complex(1.0*b[i]*b[i],0); 88 FFT(A,len,1);FFT(B,len,1); 89 for(int i=0;i<len;i++)D[i]=A[i]*B[i]; 90 FFT(D,len,-1); 91 92 memset(A,0,sizeof(A)); 93 memset(B,0,sizeof(B)); 94 for(int i=0;i<lens;i++)A[i]=complex(1.0*a[i]*a[i],0); 95 for(int i=0;i<lent;i++)B[i]=complex(1.0*b[i],0); 96 FFT(A,len,1);FFT(B,len,1); 97 for(int i=0;i<len;i++)E[i]=A[i]*B[i]; 98 FFT(E,len,-1); 99 100 for(int i=lent-1;i<lens;i++) 101 if(fabs(C[i].r-D[i].r+E[i].r)<1e-5) 102 ans[++tot]=i-lent+1; 103 104 printf("%d ",tot); 105 for(int i=1;i<=tot;i++) 106 printf("%d ",ans[i]); 107 return 0; 108 }