题意：

给定长度为n的串S和长度为m的串T，还有一个整数k
串只由ACGT组成，问T串在S串中出现了多少次，匹配机制比较特殊：
定义T[i]能匹配上S[j]，当且仅当T[i]在S[j-k,j+k]中出现过，即存在偏移位差k

数据范围：n,m,k<=2e5

解法：

基于字符集的FFT字符串匹配：
假设考虑字母C，将S串和T串中的字母C变为1，不为C的变为1，
S串是1的位置，把偏移到的位置也设为1，可以用差分实现。
将T串翻转，末尾长度不足的位置补0，
FFT可以计算出S和T的卷积F，其中S和T是01序列，F是卷积结果
如果F[i]==(T串中1的个数)，那么说明T串的每个1都被匹配到了，
说明位置i可以匹配，对4个字符都计算一遍，对可匹配位置求交集就是答案。

code：

#include<bits/stdc++.h>using namespace std;const double P=acos(-1.0);struct CC{//复数double x,y;CC(double xx=0,double yy=0){x=xx,y=yy;}CC operator+(const CC &a)const{return CC(x+a.x,y+a.y);}CC operator-(const CC &a)const{return CC(x-a.x,y-a.y);}CC operator*(const CC &a)const{return CC(x*a.x-y*a.y,x*a.y+y*a.x);}};void change(CC y[],int len){for(int i=1,j=len/2;i<len-1;i++){if(i<j)swap(y[i],y[j]);int k=len/2;while(j>=k){j-=k;k/=2;}if(j<k)j+=k;}}void fft(CC y[],int len,int on){//on为1或者-1,-1的时候表示逆变换change(y,len);for(int h=2;h<=len;h<<=1){CC wn(cos(-on*2*P/h),sin(-on*2*P/h));for(int j=0;j<len;j+=h){CC w(1,0);for(int k=j;k<j+h/2;k++){CC u=y[k];CC t=w*y[k+h/2];y[k]=u+t;y[k+h/2]=u-t;w=w*wn;}}}if(on==-1){for(int i=0;i<len;i++){y[i].x/=len;}}}//const int maxm=4e6+5;CC A[maxm],B[maxm];CC C[maxm];int mark[maxm];char s[maxm];char t[maxm];int a[maxm];int b[maxm];int n,m,k;int len;void cal(char c){for(int i=0;i<len;i++)a[i]=b[i]=0;//for(int i=0;i<n;i++){if(s[i]==c){int l=max(i-k,0);int r=min(i+k,n-1);a[l]++;a[r+1]--;}}for(int i=1;i<=n;i++)a[i]+=a[i-1];for(int i=0;i<n;i++)if(a[i])a[i]=1;//int cnt=0;//统计T串中1的个数for(int i=0;i<m;i++){if(t[i]==c){b[i]=1;cnt++;}}reverse(b,b+m);for(int i=0;i<n;i++)A[i]=CC(a[i],0);for(int i=n;i<len;i++)A[i]=CC(0,0);for(int i=0;i<m;i++)B[i]=CC(b[i],0);for(int i=m;i<len;i++)B[i]=CC(0,0);fft(A,len,1);fft(B,len,1);for(int i=0;i<len;i++)C[i]=A[i]*B[i];fft(C,len,-1);for(int i=0;i<len;i++){if((int)(C[i].x+0.5)==cnt){//如果卷积=1的个数,说明匹配上了mark[i]++;}}}signed main(){cin>>n>>m>>k;scanf("%s",s);scanf("%s",t);len=1;while(len<n*2)len<<=1;cal('A');cal('C');cal('G');cal('T');int ans=0;for(int i=m-1;i<n;i++){if(mark[i]==4)ans++;}cout<<ans<<endl;return 0;}

---