分析

我们发现难点其实是在如何处理距离为 的节点也可以匹配的问题。我们可以把四个字符拆开，一样的我们定义一个新的距离函数就可以了 。那么按照套路反转 或者 。我们就得到了一个卷积形式，那么最后的时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 8e5 + 100,P = 998244353;
int limit = 1,R[N],L = 0,K,n,m;
char A[N],B[N];
int cnt[N],g[N],f[N];
int ksm(int a,int b) {
    int x = 1;for(;b;b >>= 1,a = a * 1ll * a % P) {
        if(b & 1) x = x * 1ll * a % P;
    }return x;
}
void NTT(int *a,int type) {
    for(int i = 0;i < limit;i++) if(i < R[i]) swap(a[i],a[R[i]]);
    for(int mid = 1;mid < limit;mid <<= 1) {
        int wn = ksm(3,(P-1)/(mid << 1));
        for(int i = 0;i < limit;i += (mid << 1)) {
            for(int j = 0,w = 1;j < mid;j++,w = w * 1ll * wn % P) {
                int x = a[i + j],y = w * 1ll * a[i + j + mid] % P;
                a[i + j] = (x + y) % P;a[i + j + mid] = (x - y + P) % P;
            }  
        }
    }
    if(type == -1) {
        int Inv = ksm(limit,P - 2);reverse(a + 1,a + limit);
        for(int i = 0;i < limit;i++) a[i] = a[i] * 1ll * Inv % P;
    }
}
void solve(char pos) {
    memset(f,0,sizeof(f));memset(g,0,sizeof(g));
    for(int i = 0,last = -1e9;i < n;i++) {if(A[i] == pos) last = i;if(i - last <= K) f[i] = 1;}
    for(int i = n - 1,last = 1e9;i >= 0;i--) {if(A[i] == pos) last = i;if(last - i <= K) f[i] = 1;}
    for(int i = 0;i < m;i++) if(B[i] == pos) g[i] = 1;
    reverse(g,g + m);NTT(f,1);NTT(g,1);
    for(int i = 0;i < limit;i++) f[i] = 1ll * f[i] * g[i] % P;
    NTT(f,-1);//for(int i = 0;i < n;i++) cout << f[i] << " ";cout << endl;
    for(int i = 0;i < n;i++) cnt[i] += f[i];
}
int main() {
    scanf("%d%d%d%s%s",&n,&m,&K,A,B);
    while(limit <= n + m - 2) limit <<= 1,L++;
    for(int i = 0;i < limit;i++) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
    solve('A');solve('C');solve('G');solve('T');
    int ans = 0;
    for(int i = 0;i < n;i++) if(cnt[i] == m) ans++;
    cout << ans << endl;
}