codeforces 528D. Fuzzy Search （FFT優化DP）

題目描述

傳送門

題目大意：給出一個母串和一個模闆串，求模闆串在母串中的比對次數。

比對時，如果用s[i]比對t[j]，那麼隻要s[i-k]-s[i+k]中有字母與t[j]相同即可算作比對成功。其中s[i]表示母串的第i位，t[j]表示模闆串的第j位。

題解

如果資料範圍小的話，這題就是一個DP

f[i][j]=f[i-1][j-1]&mp[i][t[j]]表示母串的第i位比對到模闆串的第j位是否可以比對上。

其中 mp[i][j] 需要預處理,表示母串的第i位能否比對字元 j

我們要用FFT,考慮如何構造向量

我們計算的時候将所有的字元分開考慮

對于母串來說，如果第 i 位可以比對目前字元，則f[i]=1

對于模闆串來說，如果第 i 位為目前字元，則g[i]=1

令 h[i] 表示到母串的第 i 位，母串[i−m+1,i]與模闆串 [1,m] 比對可以比對上多少位，将模式串翻轉，然後将 h[i] 表示成公式就是

h[k]=∑i=0mf[k−i]∗g[i]

隻有 f[k−i] , g[i] 同時為1，即比對上的時候才能産生1的貢獻。

上面的式子可以用 FFT 在 O((n+m)log(n+m)) 的時間内出解。

然後我們統計每一位所有字元的 h[i] ，如果和為 m <script type="math/tex" id="MathJax-Element-2637">m</script>則表示在這一位可以比對上，答案+1

代碼

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cmath>  
#include<cstring>  
#define N 500003  
#define pi acos(-1)  
using namespace std;  
struct data{  
    double x,y;  
    data(double X=,double Y=) {  
        x=X,y=Y;  
    }  
}a[N*],b[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.y*b.x+a.x*b.y);    
}    
int n,m,k,n1,col[N],cl[N],mp[N][],cost[N];  
char s[N];  
int calc(char c)  
{  
    if (c=='A') return ;  
    if (c=='G') return ;  
    if (c=='C') return ;  
    if (c=='T') return ;  
}  
void clear(data a[N])
{
    for (int i=;i<=n1;i++) a[i].x=,a[i].y=;
}
void fft(data x[N],int n,int opt)  
{  
    if (n==) return;  
    data l[n>>],r[n>>];  
    for (int i=;i<n;i+=)  
     l[i>>]=x[i],r[i>>]=x[i+];  
    fft(l,n>>,opt); fft(r,n>>,opt);  
    data wn=data(cos(*pi/n),sin(*opt*pi/n));  
    data w=data(,),t;  
    for (int i=;i<n>>;i++,w=wn*w)  
     t=w*r[i],x[i]=l[i]+t,x[i+(n>>)]=l[i]-t;  
}  
int main()  
{  
    freopen("a.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);  
    scanf("%s",s); n--;  
    for (int i=;i<=n;i++) col[i]=calc(s[i]);  
    scanf("%s",s); m--;  
    for (int i=;i<=m;i++) cl[i]=calc(s[m-i]);  
    for (int i=;i<=;i++) {  
        int nxt=-;  
        for (int j=;j<=n;j++){  
            if (nxt!=-&&nxt>=j-k||col[j]==i) mp[j][i]=;  
            if (col[j]==i)  nxt=j;  
        }  
        nxt=-;  
        for (int j=n;j>=;j--) {  
            if (nxt!=-&&nxt<=j+k||col[j]==i) mp[j][i]=;  
            if (col[j]==i)  nxt=j;  
        }  
    }  
    int tot=n+m; 
    for (n1=;n1<=tot;n1<<=);  
    for (int i=;i<=;i++) {  
        clear(b); clear(a);
        for (int j=;j<=n;j++)   
         if (mp[j][i]) a[j].x=;  
         else a[j].x=;  
        for (int j=;j<=m;j++)  
         if (cl[j]==i) b[j].x=;  
         else b[j].x=;
        fft(a,n1,); fft(b,n1,);  
        for (int j=;j<=n1;j++) a[j]=a[j]*b[j];  
        fft(a,n1,-);  
        for (int j=;j<=n;j++)  
         cost[j]+=(int)(a[j].x/n1+);  
    }  
    int ans=;  
    for (int i=;i<=n;i++)  
     if (cost[i]==m+) ans++;  
    printf("%d\n",ans);  
 }