bzoj 4503: 两个串（FFT+DP）

2019-11-06 08:00:22

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题目大意：带通配符的字符串匹配，求询问串从母串中的匹配次数。母串只包含小写字母，询问串包含小写字母和通配符？，长度<=100000

题解

刚开始想了一个比较傻的方法，发现TLE了，奇慢无比。就是对于每个字符分别进行匹配。枚举当前字符，如果i母串的第i位为当前字符，那么f[i]=1;如果询问串的第j位为当前字符，g[j]=1.然后我们将询问串翻转，那么h[i]=∑nj=1f[i−j]∗g[j] $h[i]=/sum_{j=1}^n f[i-j]*g[j]$ 就表示用[i-m+1,i]去匹配，当前字符能匹配上几位。∑′z′i=′a′h[i] +k==m $/sum_{i='a'}^{'z'} h[i] /space +k==m$ 那么以这个位置为结尾可以匹配上，其中k表示通配符的个数。

这个算法在很多时候还是可以的，他的局限性在于对于每个字符都需要分开计算，对于字符集较大的字符串在时间上影响较大。

我们依然将询问串翻转，令f[i]=∑nj=1(s[i−j]−s1[j])2∗s1[j] $f[i]=/sum_{j=1}^n (s[i-j]-s1[j])^2*s1[j]$ 其中s[i]表示母串的第i位，s1[j]表示询问串的第j位，如果s1[j]=′?′ $s1[j]='?'$ ,则s1[j]=0 $s1[j]=0$ . 那么上面的式子该如何理解呢？就是要么这一位有通配符，要么能匹配上，否则求和后都不是0，如果最后f[i]=0 $f[i]=0$ 那么表示可以匹配上。我们把上面式子中的平方拆开 f[i]=∑nj=1s[i−j]2∗s1[j]+s1[j]3−2∗s[i−j]∗s1[j]2 $f[i]=/sum_{j=1}^n s[i-j]^2*s1[j]+s1[j]^3-2*s[i-j]*s1[j]^2$ 将第一项和第三项分别用FFT求解，最后把三部分合并，计算出f的值，统计答案即可。

代码

#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>#define N 500003#define pi acos(-1)#define LL long long using namespace std;struct data{ double x,y; data(double X=0,double Y=0) { x=X,y=Y; }}f[N],g[N];data Operator +(data a,data b) { return data(a.x+b.x,a.y+b.y);}data operator -(data a,data b){ return data(a.x-b.x,a.y-b.y);}data operator *(data a,data b){ return data(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}char s[N],s1[N];int n,m,a[N],b[N],L,R[N],vis[30];LL pos[N];LL pow(LL x){ return x*x;}void clear(data a[N],int n){ for (int i=1;i<=n;i++) a[i].x=a[i].y=0;}void FFT(data a[N],int opt,int n){ for (int i=0;i<n;i++) if (i>R[i]) swap(a[i],a[R[i]]); for (int i=1;i<n;i<<=1) { data wn=data(cos(pi/i),opt*sin(pi/i)); for (int p=i<<1,j=0;j<n;j+=p) { data w=data(1,0); for (int k=0;k<i;k++,w=w*wn) { data x=a[j+k],y=w*a[j+k+i]; a[j+k]=x+y; a[j+k+i]=x-y; } } } if (opt==-1) for (int i=0;i<n;i++) a[i].x/=n;}int main(){ freopen("a.in","r",stdin); freopen("my.out","w",stdout); scanf("%s",s); n=strlen(s); n--; for (int i=0;i<=n;i++) a[i]=s[i]-'a'+1; scanf("%s",s1); m=strlen(s1); m--; int cnt=0; for (int i=0;i<=m;i++) if (s1[i]=='?') b[m-i]=0,cnt++; else b[m-i]=s1[i]-'a'+1; int m1=n+m; int n1=0; for (n1=1;n1<=m1;n1<<=1) L++; for (int i=0;i<n1;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); LL sig=0; for (int i=0;i<=m;i++) sig+=(LL)pow(b[i])*b[i]; for (int i=0;i<=n;i++) f[i].x=a[i]; for (int i=0;i<=m;i++) g[i].x=pow(b[i]); FFT(f,1,n1); FFT(g,1,n1); for (int i=0;i<=n1;i++) f[i]=f[i]*g[i]; FFT(f,-1,n1); for (int i=0;i<=n;i++) pos[i]=sig-2*(LL)(f[i].x+0.5); clear(f,n1); clear(g,n1); for (int i=0;i<=n;i++) f[i].x=pow(a[i]); for (int j=0;j<=m;j++) g[j].x=b[j]; FFT(f,1,n1); FFT(g,1,n1); for (int i=0;i<=n1;i++) f[i]=f[i]*g[i]; FFT(f,-1,n1); for (int i=0;i<=n;i++) pos[i]+=(LL)(f[i].x+0.5); int ans=0; //for (int i=0;i<=n;i++) cout<<pos[i]<<" "; //cout<<endl; for (int i=0;i<=n;i++) if (!pos[i]&&i-m>=0) ans++; PRintf("%d/n",ans); for (int i=0;i<=n;i++) if (!pos[i]&&i-m>=0) printf("%d/n",i-m);}

上一篇：web第三节课作业

下一篇：Shiro自定义Ream