[Codeforces528D]Fuzzy Search（FFT）

题目描述

传送门

题意简述： 给出一个母串和一个模板串，求模板串在母串中的匹配次数。 匹配时，如果用s[i]匹配t[j]，那么只要s[i-k]-s[i+k]中有字母与t[j]相同即可算作匹配成功。其中s[i]表示母串的第i位，t[j]表示模板串的第j位。

题解

将A,G,C,T分开考虑，统计4遍，答案相加 令 F(i) 表示将小串的最后一个怼到大串的第i位最多能匹配多少个 令 f(i) 表示大串中，第i个字符是否能匹配当前字符0/1 令 g(i) 表示小串中，第i个字符是否是当前字符0/1 将小串反置，然后 F(i) 可以表示成卷积的形式 F(i)=∑j=0|T|−1f(i−j)g(j) 直接上FFT

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 1000005 const double pi=acos(-1.0); int s,t,k,ans; char S[N],T[N]; int pre[N],L,R[N],F[N]; double c[N]; struct complex { double x,y; complex(double X=0,double Y=0) { x=X,y=Y; } }a[N],b[N]; complex operator + (complex a,complex b) {return complex(a.x+b.x,a.y+b.y);} complex operator - (complex a,complex b) {return complex(a.x-b.x,a.y-b.y);} complex operator * (complex a,complex b) {return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} void FFT(complex a[N],int n,int opt) { for (int i=0;i<n;++i) if (i<R[i]) swap(a[i],a[R[i]]); for (int k=1;k<n;k<<=1) { complex wn=complex(cos(pi/k),opt*sin(pi/k)); for (int i=0;i<n;i+=(k<<1)) { complex w=complex(1,0); for (int j=0;j<k;++j,w=w*wn) { complex x=a[i+j],y=w*a[i+j+k]; a[i+j]=x+y,a[i+j+k]=x-y; } } } } void calc(int n,int m) { L=0;memset(R,0,sizeof(R)); m+=n; for (n=1;n<=m;n<<=1) ++L; for (int i=0;i<n;++i) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); FFT(a,n,1);FFT(b,n,1); for (int i=0;i<=n;++i) a[i]=a[i]*b[i]; FFT(a,n,-1); for (int i=0;i<=m;++i) c[i]=a[i].x/n+0.5; for (int i=0;i<=m;++i) F[i]+=(int)c[i]; } void solve(char now) { memset(pre,0,sizeof(pre)); for (int i=0;i<s;++i) if (S[i]==now) pre[i]=pre[i-1]+1; else pre[i]=pre[i-1]; memset(a,0,sizeof(a));memset(b,0,sizeof(b)); for (int i=0;i<t;++i) if (T[i]==now) b[i]=complex(1,0); else b[i]=complex(0,0); for (int i=0;i<s;++i) { int r=min(s-1,i+k); int l=max(0,i-k); int cnt=pre[r]; if (l) cnt-=pre[l-1]; if (cnt) a[i]=complex(1,0); else a[i]=complex(0,0); } calc(s-1,t-1); } int main() { scanf("%d%d%d",&s,&t,&k); scanf("%s",S);scanf("%s",T); for (int i=0;i<t/2;++i) swap(T[i],T[t-i-1]); solve('A');solve('G');solve('C');solve('T'); for (int i=0;i<s;++i) if (F[i]>=t) ++ans; printf("%d\n",ans); }