CF528D Fuzzy Search 字符串匹配+FFT

题意：

　　DNA序列，在母串s中匹配模式串t，对于s中每个位置i，只要s[i-k]到s[i+k]中有c就认为匹配了c。求有多少个位置匹配了t。

分析：

　　这个字符串匹配的方式，什么kmp，各种自动机都不灵。

　　所以有一个邪门功夫，fft字符串匹配。（做过洛谷《残缺的字符串》一题的应该都不陌生，带通配符的匹配字符串可以用fft卷积来做）

　　首先，由于字符集大小只有4，所以我们可以对每个字符分别考虑。

　　根据题意，对于每个字符，我们预处理a[i]数组，代表i位置是否能匹配当前字符（左右k个能匹配也算）

　　之后b[i]数组，保存t[i]位置的字符是不是c。

　　然后将b数组倒过来，fft做一下卷积，把答案累计起来检查总和是不是m就可以判断是否匹配。

代码：

 #include<bits/stdc++.h>

 #define db double

 #define cp complex<db>

 using namespace std;

 const int N=;

 const db pi=acos(-);

 int ans,ton[N],n,m,k,lm,L,r[N];

 char s[N],t[N];cp a[N],b[N];

 void init(){

     scanf("%d%d%d%s%s",&n,&m,&k,s,t);

 } void fft(cp *f,int op){

     for(int i=;i<lm;i++)

     if(i>r[i]) swap(f[i],f[r[i]]);

     for(int l=;l<lm;l<<=){

         cp wn(cos(pi/l),op*sin(pi/l));

         for(int i=;i<lm;i+=(l<<)){

             cp w(,);

             for(int j=;j<l;j++,w*=wn){

                 cp T=w*f[i+j+l];

                 f[i+j+l]=f[i+j]-T;f[i+j]+=T;

             }

         }

     } if(op==-) for(int i=;i<lm;i++) f[i]/=lm;

 } void calc(char c){

     memset(a,,sizeof(a));memset(b,,sizeof(b));

     int cnt=;

     for(int i=;i<k;i++) cnt+=(s[i]==c);

     for(int i=;i<n;i++){

         if(i+k<n) cnt+=(s[i+k]==c);

         if(i-k->=) cnt-=(s[i-k-]==c);

         a[i]=cnt>?:;cout<<a[i]<<" ";

     } for(int i=;i<m;i++) b[i]=(t[i]==c);puts("");

     fft(a,);fft(b,);

     for(int i=;i<lm;i++) a[i]*=b[i];

     fft(a,-);for(int i=;i<=n-m;i++)

     ton[i]+=(int)(a[i+m-].real()+0.5);

 } void solve(){

     for(lm=;lm<=n+m-;lm<<=,L++);

     for(int i=;i<lm;i++)

     r[i]=(r[i>>]>>)|((i&)<<(L-));

     reverse(t,t+m);calc('A');

     calc('G');calc('C');calc('T');

     for(int i=;i<=n-m;i++) if(ton[i]==m) ans++;

     printf("%d\n",ans);

 } int main(){

     init();solve();return ;

 }

fft字符串匹配

巴特西

CF528D Fuzzy Search 字符串匹配+FFT

题意：

分析：

最新文章

热门文章