一句话题意

给你两个串s、t，长度为n、m，字符集为"ATGC"，当且仅

当[i - k; i + k]中存在一个j，使得s[j ] = t[x]时，s[i ]可以

和t[x]匹配，问t总共能与s的几个子串匹配

首先，字符集只有4，那么，令s_A[i]=0/1 表示在s中i位置能否和A匹配,同理t_A[i];

一类关于通配符匹配的字符串问题都是可以用FFT来解决的

以A字符为例，令

则当c[i]==D时 以S[i]为首的一个子串内的A的位置与T的A的位置相同

令

代入原式，则

成为了卷积形式

P.S. 也可以用bitset

#include<bits/stdc++.h>

using namespace std;

namespace Tzh{

	typedef double dd;

	const char ch[]="0ATCG";

	const int maxn=700010;

	const dd pi=acos(-1);

	int ans,vis[maxn],x,y,k,rev[maxn],n=1,len,sum;

	string S,T;

	struct complex{

		dd x,y;

		complex operator +(const complex &b) const{

			return (complex){x+b.x,y+b.y};

		}

		complex operator -(const complex &b) const{

			return (complex){x-b.x,y-b.y};

		}

		complex operator *(const complex &b) const{

			return (complex){x*b.x-y*b.y,x*b.y+y*b.x};

		}

		void init(){

			x=0,y=0;

		}

	}s[maxn],t[maxn];

	void init(){

		for(int i=0;i<n;i++)

			rev[i]=rev[i>>1]>>1|((i&1)<<(len-1));

	}	

	complex omg(int x,int flag){

		return (complex){cos((dd)x*2*pi/n),(dd)sin((dd)x*2*pi/n)*flag};

	}

	void FFT(complex *a,int type){

		for(int i=0;i<n;i++) if(rev[i]>i) swap(a[i],a[rev[i]]);

		for(int l=2,m=1;l<=n;m=l,l<<=1)

			for(int i=0;i<n;i+=l)

				for(int j=0;j<m;j++){

					complex tt=omg(n/l*j,type)*a[i+j+m];

					a[i+j+m]=a[i+j]-tt,a[i+j]=a[i+j]+tt;

				}

		if(type==-1)

		for(int i=0;i<n;i++) a[i].x/=n;

	}

	void work(){

		ios::sync_with_stdio(false);

		cin>>x>>y>>k;

		cin>>S>>T; for(int i=0;i<=x;i++) vis[i]=1;

		while(n<=x+y) n<<=1,len++; init();

		for(int j=1;j<=4;j++){  int num=0;

			for(int i=0;i<S.size();i++){

				if(S[i]==ch[j]) num++;

				if(i>k&&S[i-k-1]==ch[j]) num--;

				s[i].x=(dd)(num>0);

			} num=0,sum=0;

			for(int i=S.size()-1;i>=0;i--){

				if(S[i]==ch[j]) num++;

				if(i+k+1<S.size()&&S[i+k+1]==ch[j]) num--;

				s[i].x=max(s[i].x,(dd)(num>0));

			}

			for(int i=0;i<T.size();i++)

				t[y-i-1].x=(dd)(T[i]==ch[j]),sum+=(int)t[y-i-1].x;

			FFT(s,1),FFT(t,1);

			for(int i=0;i<n;i++) s[i]=s[i]*t[i]; FFT(s,-1);

			for(int i=0;i<x;i++) if((int)((dd)s[y+i-1].x+0.5)!=sum) vis[i]=0;

			for(int i=0;i<n;i++) s[i].init(),t[i].init();

		}

		for(int i=0;i<x;i++) ans+=vis[i];

		cout<<ans<<endl;

		return ;

	}

}

int main(){

//	freopen("1.in","r",stdin);

	Tzh::work();

	return 0;

}