codeforces 528D Fuzzy Search

正解：$FFT$。

很多字符串匹配的问题都可以用$FFT$来实现。

这道题是要求在左边和右边$k$个字符内有字符和模式串匹配，那么用$kmp$是显然不行的。我们考虑把模式串翻转一下。因为只有4个字符，所以每个字符我们分开考虑。然后对于母串，如果在给定范围内有当前字符，这个位置就赋值为1；对于模式串，如果当前位置是当前字符，这个位置就赋为1。然后我们对这两个多项式做一下卷积，记录$Ans$，最后4种字符的$Ans$求和如果等于$m$，那么这个位置就是匹配的。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <complex>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <cmath>
 9 #define pi acos(-1)
10 #define inf (1<<29)
11 #define NN (1000010)
12 #define il inline
13 #define RG register
14 #define ll long long
15 #define C complex <double>
16 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
17 
18 using namespace std;
19 
20 int ans[NN],rev[NN],n,m,k,N,M,lg,pos,res;
21 char s[NN],t[NN],fg[5]="AGCT";
22 C a[NN],b[NN];
23 
24 il int gi(){
25     RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
26     if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
27 }
28 
29 il void fft(C *a,RG int n,RG int f){
30     for (RG int i=0;i<n;++i) if (i<rev[i]) swap(a[i],a[rev[i]]);
31     for (RG int i=1;i<n;i<<=1){
32     C wn(cos(pi/i),sin(f*pi/i)),x,y;
33     for (RG int j=0;j<n;j+=(i<<1)){
34         C w(1,0);
35         for (RG int k=0;k<i;++k,w*=wn){
36         x=a[j+k],y=w*a[j+i+k];
37         a[j+k]=x+y,a[j+i+k]=x-y;
38         }
39     }
40     }
41     return;
42 }
43 
44 il void work(){
45     n=gi(),m=gi(),k=gi(); scanf("%s%s",s,t); reverse(t,t+m);
46     M=n+m; for (N=1;N<=M;N<<=1) lg++;
47     for (RG int i=0;i<=N;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
48     for (RG int p=0;p<4;++p){
49     memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
50     pos=-inf;
51     for (RG int i=0;i<n;++i){
52         if (s[i]==fg[p]) pos=i;
53         if (i-pos<=k) a[i]=1;
54     }
55     pos=inf;
56     for (RG int i=n-1;i>=0;--i){
57         if (s[i]==fg[p]) pos=i;
58         if (pos-i<=k) a[i]=1;
59     }
60     for (RG int i=0;i<m;++i) if (t[i]==fg[p]) b[i]=1;
61     fft(a,N,1),fft(b,N,1); for (RG int i=0;i<N;++i) a[i]*=b[i];
62     fft(a,N,-1); for (RG int i=0;i<N;++i) ans[i]+=(int)(a[i].real()/N+0.5);
63     }
64     for (RG int i=0;i<N;++i) if (ans[i]==m) res++; printf("%d",res); return;
65 }
66 
67 int main(){
68     File("fuzzy");
69     work();
70     return 0;
71 }