本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：codeforces528D
正解：FFT
解题报告：
myy的论文题…
跟我做的上一道题一样，不同字母可以分开考虑，那么我先只考虑一种字母的情况。
我先预处理一下主串，看一下每一位能否匹配当前字母，可以的话标为$1$，否则标为$0$。
模式串中如果为当前字母标为$1$，否则标为$0$。如果我们只考虑判断模式串在某一个位置是否能匹配，那么把对应位置的乘起来再加起来，看一下和是不是等于模式串当前字母的个数，是的话就说明当前字母匹配成功了。
看到这一步，就是$FFT$的套路了…
把模式串反转，容易发现，对于同一个匹配位置的乘积，会对应到这个匹配位置上去，这就很优美了…
所以对于四个字母都$FFT$一遍，最后统计一下看每个位置的$ans$是不是等于模式串长度即可。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 700011;
int n,m,k,ans[MAXN],L,N,M,R[MAXN],tot;
char ch[MAXN],s[MAXN],zi[12]="ATGC";
C a[MAXN],b[MAXN]; inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} inline void fft(C *a,int n,int f){
for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);
for(int i=1;i<n;i<<=1) {
C wn(cos(pi/i),sin(pi*f/i)),x,t;
for(int j=0;j<n;j+=(i<<1)) {
C w(1,0);
for(int l=0;l<i;l++,w*=wn) {
x=a[j+l]; t=a[j+i+l]*w;
a[j+l]=x+t;
a[j+i+l]=x-t;
}
}
}
} inline void work(){
n=getint(); m=getint(); k=getint(); n--; m--;
scanf("%s",ch); scanf("%s",s); int last;
for(int i=0;i<=m;i++) if(i<m-i) swap(s[i],s[m-i]); else break;
M=n+m; for(L=0,N=1;N<=M;N<<=1) L++;
for(int i=0;i<N;i++) R[i]=(R[i>>1]>>1)|( (i&1) << (L-1) );
for(int l=0;l<4;l++) {
memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
last=-k-1;
for(int i=0;i<=n;i++) {
if(ch[i]==zi[l]) last=i;
if(i-last<=k) a[i]=1;
}
last=n+k+1;
for(int i=n;i>=0;i--) {
if(ch[i]==zi[l]) last=i;
if(last-i<=k) a[i]=1;
}
for(int i=0;i<=m;i++) if(s[i]==zi[l]) b[i]=1;
fft(a,N,1); fft(b,N,1);
for(int i=0;i<=N;i++) a[i]*=b[i];
fft(a,N,-1);
for(int i=m;i<=M;i++) ans[i]+=(int)(a[i].real()/N+0.5);
}
for(int i=m;i<=n;i++) if(ans[i]==m+1) tot++;
printf("%d",tot);
} int main()
{
work();
return 0;
}