题意

有两个基因串S和T，他们只包含AGCT四种字符。现在你要找出T在S中出现了几次。
有一个门限值k≥0。T在S的第i(1≤i≤|S|-|T|+1)个位置中出现的条件如下：把T的开头和S的第i个字符对齐，然后T中的每一个字符能够在S中找到一样的，且位置偏差不超过k的，那么就认为T在S的第i个位置中出现。也就是说对于所有的 j (1≤j≤|T|)，存在一个 p (1≤p≤|S|)，使得|(i+j-1)-p|≤k 和[p]=T[j]都成立。

题解

我们可以预处理出一些东西，表示某些位能不能配对$ATGC$
然后一个做法就很容易想到了
就是对于每一种字符进行一次FFT然后就可以了

然后这种题的话
因为配对方法比较奇怪，所以是不可以使用KMP进行暴力的
这个时候就可以用$shift-and$算法
可以做到$\frac{n*m}{64}$
具体思想的话还是压位
设S为原串，T为模式串
设一个状态$f$
设一个指针j扫过去
他的第i位，表示$T[0,i]$是不是$S[0,j]$的一个后缀
然后预处理一个数组B
表示S的第j为可以匹配哪一些字符
然后容易得到转移$f=(f>>1|1)$&$B[j]$
然后就可以了
这里只给出FFT的代码
Code:

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const double PI=M_PI;
struct qq {double x,y;qq() {};qq (double _x,double _y)    {
   x=_x;y=_y;}
};
qq operator + (qq x,qq y)   {
   return qq(x.x+y.x, x.y+y.y);}
qq operator - (qq x,qq y)   {
   return qq(x.x-y.x, x.y-y.y);}
qq operator * (qq x,qq y)   {
   return qq(x.x*y.x-x.y*y.y, x.x*y.y+x.y*y.x);}
const int N=200005*4;
int n,m,k;
char ss[N],ss1[N];
qq a[N],b[N];
int now;
int bin[N];
void fft (qq *a,int n,int o)
{for (int u=0;u<n;u++) bin[u]=(bin[u>>1]>>1)|((u&1)*(n>>1));for (int u=1;u<n;u++)if (u<bin[u])swap(a[u],a[bin[u]]);for (int u=1;u<n;u<<=1){qq wn=qq(cos(2*PI/(u<<1)),o*sin(2*PI/(u<<1)));for (int i=0;i<n;i+=(u<<1)){qq w=qq(1,0);for (int j=0;j<u;j++){qq t=w*a[u+i+j];a[u+i+j]=a[i+j]-t;a[i+j]=a[i+j]+t;w=w*wn;}}}
}
int f[N];
void solve (char x)
{memset(a,0,sizeof(a));memset(b,0,sizeof(b));int mx=-1;for (int u=0;u<=n;u++)  {if (ss[u]==x)   mx=u+k;if (u<=mx) a[u].x=1;}mx=n+1;for (int u=n;u>=0;u--){if (ss[u]==x) mx=u-k;if (u>=mx) a[u].x=1;}for (int u=0;u<=m;u++)if (ss1[u]==x)  b[u].x=1;
/* for (int u=0;u<now;u++) printf("%lf ",a[u].x);printf("\n");for (int u=0;u<now;u++) printf("%lf ",b[u].x);printf("\n");*/for (int u=0;u<=n/2;u++) swap(a[u],a[n-u]);fft(a,now,1);fft(b,now,1);for (int u=0;u<now;u++) a[u]=a[u]*b[u];fft(a,now,-1);
/* for (int u=0;u<now;u++) printf("%d ",(int)(a[u].x/now+0.5));printf("\n");system("pause");*/for (int u=0;u<=n;u++)  f[n-u]=f[n-u]+(int)(a[u].x/now+0.5);/*for (int u=0;u<=n;u++)printf("%d ",f[u]);*/
}
int main()
{scanf("%d%d%d",&n,&m,&k);n--;m--;now=1;while (now<=n+m) now<<=1;scanf("%s%s",ss,ss1);solve('A');solve('T');solve('G');solve('C');
/* for (int u=0;u<=n;u++)printf("%d ",f[u]);*/int ans=0;for (int u=0;u<=n;u++)if (f[u]==m+1)ans++;printf("%d\n",ans); return 0;
}