给定母串\(S\)和模式串\(T\)，字符集大小为\(4\),给定\(k\)，\(T\)在某个位置\(i\)匹配，当且仅当\(\forall\; j\in [0, |T|-1], \exists p\in [i-k, i+k]\)使得\(T_j=S_{i+p+j}\),求\(T\)的匹配次数

\(|S|, |T|\le 2*{10}^5\)

令\(|T|=m\),

对于每个字符\(c\),令\(a[i]=[S_i\)能匹配\(c]\)，\(b[i]=[T_i == c]\)

贡献\(f[j]=\sum_{i=0}^{m-1}a[j+i]*b[i]\)，当总贡献为\(m\)时\(j\)位置为匹配位置

令\(d[i]=b[m-i-1]\),即\(d[m-i-1]=b[i]\),

则\[f[j]=\sum_{i=0}^{m-1}a[j+i]*d[m-i-1]=(a*d)(j+m-1)\]

计算卷积就好

char s[Maxn], t[Maxn];int q[Maxn], head, tail, tot[Maxn];void cal(char c){    memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g));    head=1, tail=0;    for(int i=0; i < n; i++){        if(s[i] == c) q[++tail]=i;        while(head <= tail && q[head]+k < i) head++;        if(head <= tail) f[i].a=1;    }head=1, tail=0;    for(int i=n-1; i >= 0; i--) {        if(s[i] == c) q[++tail]=i;        while(head <= tail && q[head] > i+k) head++;        if(head <= tail) f[i].a=1;    }    for(int i=0; i < m; i++) if(t[i] == c) g[m-i-1].a=1;    FFT(f, 1); FFT(g, 1); for(int i=0; i < lim; i++) f[i]=f[i]*g[i]; FFT(f, -1);    for(int i=0; i < n; i++) tot[i]+=floor(f[i+m-1].a/lim+0.5);}void solve(){    n=read(), m=read(), k=read(); scanf("%s", s); scanf("%s", t);    while(lim <= n+m-2) lim<<=1, l++;    for(int i=0; i < lim; i++) r[i]=r[i>>1]>>1|((i&1)<
    
     = m) ans++;    printf("%d", ans);}
    

（我真是个小天才，用\(char\)来存数组\(orz\)）