题目大意
给定文本串(S)，匹配串(T)，和一个非负整数(k)。
如果在(S_{i-k})至(S_{i+k})内有与(T_j)相同的字符，则称(S_i)与(T_j)可以匹配。
求有多少个子串与(T)相匹配。
题目分析
与【BZOJ3160】万径人踪灭方法相似。
我们可以先预处理出哪些位置匹配的上，然后作4次FFT结果相加即可。
代码实现
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<complex>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=200005,M=N<<2;
using namespace std;
inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
typedef complex<double> Z;
const double pi=acos(-1);
void FFT(Z *a,int x,int K){
static int rev[M],lst;
int n=1<<x;
if(n!=lst){
for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<x-1);
lst=n;
}
for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int i=1;i<n;i<<=1){
int tmp=i<<1;
Z wn(cos(pi/i),sin(pi*K/i));
for(int j=0;j<n;j+=tmp){
Z w(1,0);
for(int k=0;k<i;k++,w=w*wn){
Z x=a[j+k],y=a[i+j+k]*w;
a[j+k]=x+y,a[i+j+k]=x-y;
}
}
}
if(K==-1)for(int i=0;i<n;i++)a[i]/=n;
}
Z a[M],b[M],ans[M];
int Get(char ch){if(ch=='A')return 0;if(ch=='C')return 1;if(ch=='G')return 2;return 3;}
int num[4];bool ok[4][N];
char S[N],T[N];
int main(){
int l1=Getint(),l2=Getint(),K=Getint();
scanf("%s%s",S,T);
for(int i=0,l=0,r=-1;i<l1;i++){
while(r+1<l1&&r<i+K)num[Get(S[++r])]++;
while(l<i-K)num[Get(S[l++])]--;
for(int j=0;j<4;j++)ok[j][i]=(num[j]>0);
}
reverse(T,T+l2);
int x=ceil(log2(l1+l2+1));
fill(ans,ans+(1<<x),0);
for(int t=0;t<4;t++){
fill(a,a+(1<<x),0),fill(b,b+(1<<x),0);
for(int i=0;i<l1;i++)a[i]=Z(ok[t][i],0);
for(int i=0;i<l2;i++)b[i]=Z((Get(T[i])==t),0);
FFT(a,x,1),FFT(b,x,1);
for(int i=0;i<(1<<x);i++)ans[i]+=a[i]*b[i];
}
FFT(ans,x,-1);
int ret=0;
for(int i=l2-1;i<l1;i++)ret+=(((int)(ans[i].real()+0.5))==l2);
cout<<ret;
return 0;
}