https://acm.hdu.edu.cn/showproblem.php?pid=6975
题意:
给出2个串S和T,含有通配符。
若S的一个子串满足和T不匹配的位置<=k个,则认为S的这个子串与T是匹配的
对于k∈[0,|T|],回答S中有多少个子串与T匹配
解决这道问题首先要明白如何用FFT求解字符串匹配问题
可以看 https://www.cnblogs.com/TheRoadToTheGold/p/15128004.html
假设没有通配符
对于这个问题,我们可以求出S的每个长为|T|的子串与T的匹配位置有多少个
若有x个,那么对于S的这个长为|T|的子串,k要>=|T|-x,这个子串才能与T匹配
|T|-x是最小的满足要求的k,我们求最小的有多少个,做前缀和统计即可
如何求S的每个长为|T|的子串与T的匹配位置有多少个?
枚举c=0—9,S和T的对应位置是c,令其为1,不是c,令其为0,做FFT,即可求出这个字符c的匹配位置数量
所有的累加即可
加上通配符
简单容斥一下
那么匹配位置数量=不计算通配符的数量 + S的这个子串通配符数量 + T含有的通配符数量 - S的这个子串和T匹配的通配符数量
一个串的通配符数量用前缀和可以求
两个串对应匹配的通配符数量,还是FFT
#include<bits/stdc++.h> using namespace std; const int N=(1<<19)+3; const double pi=acos(-1); char s[N],t[N]; int f[N]; int fs[N]; int ans[N]; int rev[N]; struct Complex { double x,y; Complex(double x_=0,double y_=0):x(x_),y(y_){} Complex operator + (Complex P) { return Complex(x+P.x,y+P.y); } Complex operator - (Complex P) { return Complex(x-P.x,y-P.y); } Complex operator * (Complex P) { return Complex(x*P.x-y*P.y,x*P.y+y*P.x); } }; typedef Complex E; E a1[N],a2[N]; void fft(E *a,int len,int type) { for(int i=0;i<len;++i) if(i<rev[i]) swap(a[i],a[rev[i]]); for(int i=1;i<len;i<<=1) { E wn(cos(pi/i),type*sin(pi/i)); for(int p=i<<1,j=0;j<len;j+=p) { E w(1,0); for(int k=0;k<i;++k,w=w*wn) { E x=a[j+k],y=a[j+k+i]*w; a[j+k]=x+y; a[j+k+i]=x-y; } } } if(type==-1) for(int i=0;i<len;++i) a[i].x/=len; } void FFT(E *a,E *b,int len,int kk) { fft(a,len,1); fft(b,len,1); for(int i=0;i<len;++i) a[i]=a[i]*b[i]; fft(a,len,-1); // for(int i=0;i<len;++i) printf("%d ",(int)(a[i].x+0.5)); // printf("\n\n\n"); for(int i=0;i<len;++i) f[i]+=kk*((int)(a[i].x+0.5)); } int main() { // freopen("1003.in","r",stdin); // freopen("answew0.txt","w",stdout); // printf("111111\n\n"); int T,n,m,len,num,bit,tmp,ft; char c; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); scanf("%s",s); scanf("%s",t); reverse(t,t+m); num=m+n-1; len=1; bit=0; while(len<num) len<<=1,bit++; for(int i=0;i<len;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1); for(int i=0;i<len;++i) f[i]=0; for(int i=0;i<=10;++i) { c='0'+i; if(i==10) c='*'; for(int j=0;j<len;++j) a1[j]=a2[j]=E(0,0); for(int j=0;j<n;++j) a1[j].x= s[j]==c ? 1 : 0; for(int j=0;j<m;++j) a2[j].x= t[j]==c ? 1 : 0; if(i!=10) FFT(a1,a2,len,1); else FFT(a1,a2,len,-1); // for(int j=0;j<n;++j) printf("%d ",f[j]); // printf("\n"); } fs[0]= s[0]=='*' ? 1 : 0; for(int i=1;i<n;++i) fs[i]=fs[i-1]+(s[i]=='*'); ft= t[0]=='*' ? 1 : 0; for(int i=1;i<m;++i) ft+=(t[i]=='*'); fill(ans,ans+m+1,0); for(int i=0;i+m-1<n;++i) { tmp=f[i+m-1]+fs[i+m-1]-(i ? fs[i-1] : 0)+ft; ans[m-tmp]++; } for(int i=1;i<=m;++i) ans[i]+=ans[i-1]; for(int i=0;i<=m;++i) printf("%d\n",ans[i]); } }