[CF 528D] Fuzzy Search

作法：

蠻經典的 FFT 題。（以下使用 0 base ）因為只要注意到， $T$ 不能放在 $i$ 位置的充要條件是：存在 $j$ 滿足 $S[i+j]$ 的前後 $k$ 個之中沒有字母 $T[ j ]$ 。因此首先把每個字母分開考慮，對於每個字母 $c$ 可以先 $O( |S| )$ 處理出「哪些位置的前後 $k$ 個之中沒有 $c$ 」，這只要先算出「前 $i$ 個字母中有幾個 $c$ 」就可以 $O( 1 )$ 知道一個區間裡是否有 $c$ 了。假設所有上面所說的位置為 $a_1$ ~ $a_k$ ，還有 $T$ 中的所有 $c$ 的出現位置 $b_1$ ~ $b_r$ ，那麼考慮一個多項式 $f( x ) = x^{a_1} + x^{a_2} + ... + x^{a_k}$ ，還有$g( x ) = x^{ m-1-b_1 } + x^{ m-1-b_2 } + ... + x^{ m-1-b_r }$（其中 $m = | T |$），那麼如果 $f( x ) * g( x )$ 的 $x^i$ 係數不為 $0$ 的話，就代表把 $T$ 放在 $i - m + 1$ 位置時是不合法的。因此只要作四次多項式乘法，把他全部加起來，然後去看冪次 $m-1$ ~ $n-1$ 中有幾個係數為$0$的項就可以了。

code :

#include<bits/stdc++.h>
#define DB double
#define comp complex<DB>
using namespace std;
const int maxn=1<<19 ;
const DB PI=2*acos(0.0) ;
 
comp tmp[maxn] ;
void DFT(comp *a,int n,int idft)
{
    if(n==1) return ;
    for(int i=0;i<n;i++) tmp[i]=a[i] ;
    for(int i=0;i<n;i++) a[i%2 ? n/2+i/2 : i/2]=tmp[i] ;
    comp *a1=a , *a2=a+n/2 ;
    DFT(a1,n/2,idft) ;
    DFT(a2,n/2,idft) ;
    comp w(cos(2*PI/n),sin(2*PI/n)) , now(1,0) ;
    if(idft) w=conj(w) ;
    for(int i=0;i<n/2;i++,now*=w)
    {
        tmp[i]=a1[i]+now*a2[i] ;
        tmp[i+n/2]=a1[i]-now*a2[i] ;
    }
    for(int i=0;i<n;i++) a[i]=tmp[i] ;
}
 
void mul(comp *a,comp *b,comp *c,int n)
{
    DFT(a,n,0) ;
    DFT(b,n,0) ;
    for(int i=0;i<n;i++) c[i]=a[i]*b[i] ;
    DFT(c,n,1) ;
    for(int i=0;i<n;i++) c[i]/=n ;
}
 
comp a[maxn],b[maxn],ans[maxn] ;
char s[maxn],t[maxn] ;
int sum[maxn],n,m,k ;
 
void solve(char ch)
{
    for(int i=0;i<maxn;i++) a[i]=b[i]=(comp){0,0} ;
    for(int i=0;i<m;i++) if(t[i]==ch) b[m-1-i]=(comp){1,0} ;
    for(int i=0;i<n;i++) sum[i+1]=sum[i]+(s[i]==ch) ;
    for(int i=0;i<n;i++) if(sum[min(i+k,n-1)+1]==sum[max(i-k,0)])
        a[i]=(comp){1,0} ;
    mul(a,b,a,maxn) ;
    for(int i=0;i<maxn;i++) ans[i]+=a[i] ;
}
 
main()
{
    scanf("%d%d%d%s%s",&n,&m,&k,s,t) ;
    for(int i=0;i<4;i++) solve("ATCG"[i]) ;
    int cnt=0 ;
    for(int i=m-1;i<=n-1;i++) if(int(real(ans[i])+0.5)==0)
        cnt++ ;
    printf("%d\n",cnt) ;
}