首页 > 代码库 > BZOJ 4503 两个串（FFT）
BZOJ 4503 两个串（FFT）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4503
【题目大意】
给出S串和T串，计算T在S中出现次数，T中有通配符‘?‘。
【题解】
我们定义f[x]=sum_{i=0}^{n-1}|s1[i]-s2[i]|，当f[x]=0时，两个字符串相等。因为考虑到这里还有适配符，所以用f[x]=sum_{i=0}^{n-1}(s1[i]-s2[i])*(s1[i]-s2[i])*s1[i]*s2[i]来表示匹配函数。我们可以发现，如果将一个串倒置，那么这就是一个卷积的式子。因此我们将多项式展开，将得到的相加的三段式子，做三次FFT，将结果汇总，然后统计即可。
【代码】
#include <cstdio>#include <cmath>#include <algorithm>#include <cstring> using namespace std;typedef long long LL;const int N=1048600;int n,pos[N];namespace FFT{ struct comp{ double r,i; comp(double _r=0,double _i=0):r(_r),i(_i){} comp operator +(const comp&x){return comp(r+x.r,i+x.i);} comp operator -(const comp&x){return comp(r-x.r,i-x.i);} comp operator *(const comp&x){return comp(r*x.r-i*x.i,i*x.r+r*x.i);} comp conj(){return comp(r,-i);} }A[N],B[N]; const double pi=acos(-1.0); void FFT(comp a[],int n,int t){ for(int i=1;i<n;i++)if(pos[i]>i)swap(a[i],a[pos[i]]); for(int d=0;(1<<d)<n;d++){ int m=1<<d,m2=m<<1; double o=pi*2/m2*t; comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2){ comp w(1,0); for(int j=0;j<m;j++){ comp& A=a[i+j+m],&B=a[i+j],t=w*A; A=B-t;B=B+t;w=w*_w; } } }if(t==-1)for(int i=0;i<n;i++)a[i].r/=n; }}int l1,l2,ans[N],cnt=0,a[N],b[N];FFT::comp A[N],B[N],C[N];char s1[N],s2[N];int main(){ scanf(" %s %s",&s1,&s2); l1=strlen(s1); l2=strlen(s2); for(int i=0;i<l1;i++)a[i]=s1[i]-‘a‘+1; for(int i=0;i<l2;i++)b[l2-1-i]=s2[i]==‘?‘?0:s2[i]-‘a‘+1; int N=1; while(N<l1+l2)N<<=1; int j=__builtin_ctz(N)-1; for(int i=0;i<N;i++){pos[i]=pos[i>>1]>>1|((i&1)<<j);} for(int i=0;i<N;i++)A[i]=FFT::comp(a[i]*a[i]*a[i],0),B[i]=FFT::comp(b[i],0); FFT::FFT(A,N,1);FFT::FFT(B,N,1); for(int i=0;i<N;i++)C[i]=C[i]+A[i]*B[i]; for(int i=0;i<N;i++)A[i]=FFT::comp(a[i],0),B[i]=FFT::comp(b[i]*b[i]*b[i],0); FFT::FFT(A,N,1);FFT::FFT(B,N,1); for(int i=0;i<N;i++)C[i]=C[i]+A[i]*B[i]; for(int i=0;i<N;i++)A[i]=FFT::comp(a[i]*a[i],0),B[i]=FFT::comp(b[i]*b[i],0); FFT::FFT(A,N,1);FFT::FFT(B,N,1); for(int i=0;i<N;i++)C[i]=C[i]-A[i]*B[i]*FFT::comp(2,0); FFT::FFT(C,N,-1); for(int i=l2-1;i<l1;i++){ if(C[i].r<0.5)ans[cnt++]=i-l2+1; }printf("%d\n",cnt); for(int i=0;i<cnt;i++)printf("%d\n",ans[i]); return 0;}
BZOJ 4503 两个串（FFT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。