Problem
Description
你有一个长度为 (n) 的串 (S)，以及长度为 (m) 的串 (T)。
现给定一个数 (k) ，我们说 (T) 在 (S) 的位置 (i) 匹配上，当且仅当对于每一个 (1le ale m) ，都有一个位置 (1le ble n) 满足 (|(i+a-1)-b|le k) ，且 (S_b=T_a) 。
请回答 (T) 在 (S) 中匹配上了多少个不同的位置。
Range
(n,m,kle2*10^5)
Algorithm
多项式
Mentality
思路很妙的说。
先考虑 (k=0) 的情况。不难发现，当 (T) 与 (S) 匹配上时，(T) 中的每个字符与 (S) 中对应匹配字符的 位置的差 是相等的。
同时考虑在多项式乘法中，若许多对项最后会贡献在同一个位置上，那么它们的 次方的和 是相等的。
则考虑倒转原串，得到 (T') 。
由于字符集大小仅仅为 (4) ，我们可以尝试一下分开考虑每种不同的字符。
对于当前字符 (c)，考虑设 (f_i=[S_i==c]*x^i)，(g_i=[T'_i==c]*x^i)。
则对于得到的 (F(x)=f(x)*g(x)) 而言，我们发现对于原串中的字符 (S_i=T_j=c) ，它们在 (f) 与 (g) 中对应项的乘积为 (1) ，且对位置 (m-j+1+i) 产生了 (1) 的贡献。
对于下一种字符 (p) 而言，若有 (S_{i+1}=T_{j+1}=p)，则会对 (m-(j+1)+1+(i+1)=m-j+1+i) 有 (1) 的贡献。
换句话说，若有 (T) 在 (S) 的位置 (i) 匹配上了，那么必定有：(T_1=S_i,T_2=S_{i+1}dots T_m=S{i+m-1}) ，也就必定会在对四种字符的卷积里对 (m-j+1+i) 这一项总共产生 (m) 的贡献。
将四次卷积的结果相加，则最后的答案为：系数为 (m) 的项的个数。
接着考虑 (k>0) 的情况，我们会发现和 (k=0) 的思路几乎一致，对于这个 (k) ，想想它的意义：我们在处理每种不同的字符的时候，若当前字符为 (c) ，对于每个为 (c) 的位置，它往左右两边 (k) 位也都是可以匹配的位置。
那我们直接将每个 (c) 的左右 (k) 位也都设成 (c) 不就好了嘛？
那么思路就很清晰了：四种字符分别统计，然后对于每种当前统计的字符，将左右 (k) 位设为同样的字符，得到 (f,g) 两个多项式，并将其卷积得到 (F(x)=f(x)*g(x)) ，将四个 (F(x)) 相加，统计系数为 (m) 的项数。
完毕。
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
#define go(x, i, v) for (int i = hd[x], v = to[i]; i; v = to[i = nx[i]])
#define inline __inline__ __attribute__((always_inline))
LL read() {
long long x = 0, w = 1;
char ch = getchar();
while (!isdigit(ch)) w = ch == '-' ? -1 : 1, ch = getchar();
while (isdigit(ch)) {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * w;
}
const int Max_n = 2e5 + 5, mod = 998244353, G = 3;
int n, m, K, ans;
int f[Max_n << 2], g[Max_n << 2], A[Max_n << 2];
int lim, bit, rev[Max_n << 2];
char S[Max_n], T[Max_n];
inline void Convert(char &c) {
if (c == 'A') c = 'a';
if (c == 'C') c = 'b';
if (c == 'G') c = 'c';
if (c == 'T') c = 'd';
}
inline int ksm(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = 1ll * a * a % mod)
if (b & 1) res = 1ll * res * a % mod;
return res;
}
namespace NTT {
inline void dft(int *f, bool t) {
for (int i = 0; i < lim; i++)
if (rev[i] > i) swap(f[i], f[rev[i]]);
for (int len = 1; len < lim; len <<= 1) {
int Wn = ksm(G, (mod - 1) / (len << 1));
if (t) Wn = ksm(Wn, mod - 2);
for (int i = 0; i < lim; i += len << 1) {
int Wnk = 1;
for (int k = i; k < i + len; k++, Wnk = 1ll * Wnk * Wn % mod) {
int x = f[k], y = 1ll * f[k + len] * Wnk % mod;
f[k] = (x + y) % mod, f[k + len] = (x - y + mod) % mod;
}
}
}
}
} // namespace NTT
inline void ntt(int *f, int *g) {
NTT::dft(f, 0), NTT::dft(g, 0);
for (int i = 0; i < lim; i++) f[i] = 1ll * f[i] * g[i] % mod;
NTT::dft(f, 1);
int Inv = ksm(lim, mod - 2);
for (int i = 0; i < lim; i++) f[i] = 1ll * f[i] * Inv % mod;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("D.in", "r", stdin);
freopen("D.out", "w", stdout);
#endif
n = read(), m = read(), K = read();
scanf(" %s", S + 1), scanf("%s", T + 1);
for (int i = 1; i <= n; i++) Convert(S[i]);
for (int i = 1; i <= m; i++) Convert(T[i]);
for (int i = 1; i <= m / 2; i++) swap(T[i], T[m - i + 1]);
bit = log2(n + m) + 1, lim = 1 << bit;
for (int i = 0; i < lim; i++)
rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (bit - 1));
for (int k = 'a'; k <= 'd'; k++) {
memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g));
for (int i = 1, cnt = 0; i <= n; i++) {
if (S[i] == k)
cnt = K, f[i] = 1;
else if (cnt)
cnt--, f[i] = 1;
}
for (int i = n, cnt = 0; i >= 1; i--) {
if (S[i] == k)
cnt = K, f[i] = 1;
else if (cnt)
cnt--, f[i] = 1;
}
for (int i = 1; i <= m; i++) g[i] = T[i] == k;
ntt(f, g);
for (int i = 0; i < lim; i++) A[i] += f[i];
}
for (int i = 0; i < lim; i++)
ans += A[i] == m;
cout << ans;
}