首页 > 代码库 > Bzoj4503 两个串
Bzoj4503 两个串
Submit: 398 Solved: 190
Description
兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，
分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。
Input
两行两个字符串，分别代表S和T
Output
第一行一个正整数k，表示T在S中出现了几次
接下来k行正整数，分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出，S下标从0开始。
Sample Input
bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab
a?aba?abba
a?aba?abba
Sample Output
0
HINT
S 长度不超过 10^5， T 长度不会超过 S。 S 中只包含小写字母， T中只包含小写字母和“?”
Source
数学 FFT 字符串 脑洞题
通配符的出现使得自动机失去了用武之地。DP虽然还能得出正确的结果，但是却要跑一年。
盟军急需找到新的匹配手段（雾）
如何判断两个字符相等？它们的编码相等时它们就相等了(废话)
如何判断两个字符串相等？它们对应每一位的编码都相等时它们就相等了(废话)
a=b有什么性质？a-b=0 (废话)
那么两个字符串相等时有Σ(a[i]-b[i])=0 (诶？)
当然Σ(a[i]-b[i])=0不一定代表两串相等，可能前面多了一点，后面少了一点，加起来为0。
平方！ Σ((a[i]-b[i])^2)==0，没有漏洞了。
那么我们得到一种新的匹配方式，它比起旧匹配方式……不但没有优化，还多了平方的操作。
但如果将b数组翻转，似乎……可以求卷积！
激动地将式子展开，得到 Σa[i]*a[i] + Σb[i]*b[i] -Σ 2*a[i]*b[i] ，分别求三部分的卷积并累加，如果最终结果为0，说明字符串匹配上了！
通配符怎么解决？设通配符的值为0，在上面多乘一个b[i]得到Σ( b[i]*(a[i]-b[i])^2)==0 (当b[i]==0或b[i]==a[i]时可以匹配)。
FFT求卷积(O(nlogn))，若结果的第i位是0，那么(i-len(b)+1)到i这一段可以匹配。
マジやばくねー
注意精度误差。
还要注意数组重复利用时的初始化……前期代码写太乱各种WA，最后一气之下从0到n全部重新覆盖……
题目加强版：http://www.cnblogs.com/SilverNebula/p/6511348.html
↑这一版代码比下面这个优化程度高很多
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<complex> 9 using namespace std;10 const double pi=acos(-1.0);11 const int mxn=810010;12 typedef complex<double>com;13 int read(){14 int x=0,f=1;char ch=getchar();15 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}16 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}17 return x*f;18 }19 int rev[mxn];20 int n,l;21 void FFT(com *a,int flag){22 int i,j,x;23 for(i=0;i<n;i++)24 if(rev[i]>i)swap(a[rev[i]],a[i]);25 for(i=1;i<n;i<<=1){26 com wn(cos(pi/i),flag*sin(pi/i));27 for(j=0;j<n;j+=(i<<1)){28 com w(1,0);29 for(int k=0;k<i;k++,w*=wn){30 com x=a[j+k],y=w*a[i+j+k];31 a[j+k]=x+y;32 a[i+j+k]=x-y;33 }34 }35 }36 if(flag==-1)for(i=0;i<n;i++)a[i]/=n;37 }38 char s1[mxn],s2[mxn];39 double a[mxn],b[mxn];40 com c[mxn],d[mxn];41 com e[mxn],two;42 int ans[mxn],cnt=0;43 int main(){44 int i,j;45 scanf("%s",s1);46 scanf("%s",s2);47 int len=strlen(s1); int l2=strlen(s2);48 int m=len<<1;49 for(n=1;n<m;n<<=1)l++;50 for(i=0;i<n;i++){rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));}51 //52 reverse(s2,s2+l2);53 for(i=0;i<len;i++)a[i]=s1[i]-‘a‘+1;54 for(i=0;i<l2;i++)if(s2[i]==‘?‘)b[i]=0;else b[i]=s2[i]-‘a‘+1;55 // 56 for(i=0;i<n;i++)c[i]=com(b[i]*b[i]*b[i],0);//b^357 for(i=0;i<n;i++)d[i]=com(1,0);58 FFT(c,1);FFT(d,1);59 for(i=0;i<n;i++)e[i]=c[i]*d[i];60 for(i=0;i<n;i++)c[i]=com(a[i]*2,0);61 for(i=0;i<n;i++)d[i]=com(b[i]*b[i],0);62 FFT(c,1);FFT(d,1);63 for(i=0;i<n;i++)e[i]-=c[i]*d[i];64 for(i=0;i<n;i++)c[i]=com(a[i]*a[i],0);65 for(i=0;i<n;i++)d[i]=com(b[i],0);66 FFT(c,1);FFT(d,1);67 for(i=0;i<n;i++)e[i]+=c[i]*d[i];68 FFT(e,-1);69 for(i=l2-1;i<len;i++){70 if(abs(e[i].real())<0.5){71 ans[++cnt]=i-l2+1;72 }73 }74 printf("%d\n",cnt);75 for(i=1;i<=cnt;i++){76 printf("%d\n",ans[i]);77 }78 return 0;79 }
Bzoj4503 两个串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。