C++(g++ 7.5.0) 解法, 执行用时: 2084ms, 内存消耗: 51784K, 提交时间: 2022-10-19 16:50:48

#include <bits/stdc++.h>
#define IOS   ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define xs(a) cout<<setiosflags(ios::fixed)<<setprecision(a);
#define FOR(i, a, b) for (ll (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (ll (i) = (a); (i) >= (b); (i)--)
using namespace std;
#define ull unsigned long long
#define ll long long
typedef pair<ll,ll> pll;
const int N=2e6+5;
const int mod=1e9+7;
/*-----------------------------------------------------------------------------------------------*/
typedef complex<double> com;
const double pi = acos(-1.0);
ll rev[N];
//  fft部分
inline void fft(com *a,int len,int type){
	for(int i=0;i<len;i++){
		if(i<rev[i])	swap(a[i],a[rev[i]]);
	}
	for(int mid=1;mid<len;mid<<=1){
		com W(cos(pi/mid),type*sin(pi/mid));
		for(int j=0;j<len;j+=mid<<1){
			com w(1,0);
			for(int k=0;k<mid;k++){
				com x=a[j+k],y=w*a[j+mid+k];
				a[j+k]=x+y;
				a[j+mid+k]=x-y;
				w=w*W;
			}
		}
	}
}
com a[N],b[N];
ll d[N],cnt[N];
string s,t;
ll n,m,k;
ll M=1;
void cal(char c){
    FOR(i,0,M)a[i]=b[i]=com(0,0),d[i]=0;
    ll sz=s.size();
    for(ll i=0;i<sz;i++){
        if(s[i]==c){
            ROF(j,min(i+k,sz),max(i-k,0ll)){
                if(d[j])break;
                d[j]=1;
            }
        }
    }
    for(int i=0;i<sz;i++){
        if(d[i])a[i]=com(1,0);
    }
    ll tz=t.size();
    for(int i=0;i<m;i++){
        if(t[i]==c)b[m-i-1]=com(1,0);
    }
    fft(a,M,1);fft(b,M,1);
    for(int i=0;i<M;i++)a[i]=a[i]*b[i];
    fft(a,M,-1);
    for(int i=0;i<n;i++)cnt[i]+=int(a[i].real()/M+0.5);
}

signed main(){
    cin>>n>>m>>k;
    cin>>s>>t;
    ll l=0;
    while(M<=(n+m)*2)	M<<=1,l++;
    for(int i=0;i<M;++i)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    cal('A');cal('G');cal('C');cal('T');
    ll ans=0;
    for(int i=0;i<n;i++) if(cnt[i]==m)ans++;
    cout<<ans<<endl;



    return 0;
}

C++ 解法, 执行用时: 962ms, 内存消耗: 4288K, 提交时间: 2022-02-24 21:30:19

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int mp[200],a[N][4];
bitset<N> bs[4],ans;
int main()
{
	ios::sync_with_stdio(false);
	int n,m,k;
	string s,t;
	cin>>n>>m>>k>>s>>t;
	mp['A']=0,mp['C']=1,mp['G']=2,mp['T']=3;
	for(int i=0;i<n;i++)
	{
		a[max(0,i-k)][mp[s[i]]]++;
		a[min(n,i+k+1)][mp[s[i]]]--;
	}
	for(int i=0;i<n;i++)
	{
		ans[i]=1;
		for(int j=0;j<4;j++)
		{
			if(i)
				a[i][j]+=a[i-1][j];
			if(a[i][j])	
				bs[j][i]=1;
			else
				bs[j][i]=0;
		}
	}
	for(int i=0;i<m;i++)
		ans&=(bs[mp[t[i]]]>>i);
	int sum=0;
	for(int i=0;i<n;i++)
		sum+=(ans[i]==1);
	printf("%d\n",sum);
	return 0;
}