一开始看错题了，看了好久才发现就是个板子。。。
这个东西本质上是循环移位，我们考虑在 \(S\) 前后各添加 \(W - 1\) 个 .，例如 \(W = 5, S = \texttt{ABC}\) 时，添加后 \(S = \texttt{....ABC....}\)。此时我们发现 \(S\) 的每个长度为 \(W\) 的子串一一对应一个显示在公告板上的串。那么这就是一个带通配符字符串匹配问题。
接下来直接套 P4173 残缺的字符串即可。展开讲的话，设 \(n = |s|, m = |t|\)，并且 \(t\) 要匹配 \(s\)。那我们把通配符的值设成 \(0\) 后，设 \(f_i = \sum\limits_{j = 1}^m t_j (s_{i - m + j} - t_j)^2\)，那么 \(s_{i - m + 1 \sim i}\) 能匹配 \(t\) 当且仅当 \(f_i = 0\)。把平方拆开，就是若干个减法卷积。考虑翻转 \(t\)，做加法卷积即可。
时间复杂度是 \(O(n \log n)\)，带一个巨大常数。
这题用 NTT 会有些难受，因为 \(f_i\) 能达到 \(5 \times 10^9\)，为了保证正确性必须要写双模数（我写的双模数还 T 了），FFT 比 NTT 快很多（可能是我 NTT 的实现劣了），所以我使用的是 FFT。
code
// Problem: Ex - Marquee
// Contest: AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307)
// URL: https://atcoder.jp/contests/abc307/tasks/abc307_h
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2100100;
const db pi = acos(-1);
int n, m, mp[128], a[maxn], b[maxn], r[maxn];
db f[maxn], g[maxn];
char s[maxn], t[maxn];
struct comp {
db x, y;
comp(db a = 0, db b = 0) : x(a), y(b) {}
};
typedef vector<comp> poly;
inline comp operator + (const comp &a, const comp &b) {
return comp(a.x + b.x, a.y + b.y);
}
inline comp operator - (const comp &a, const comp &b) {
return comp(a.x - b.x, a.y - b.y);
}
inline comp operator * (const comp &a, const db &b) {
return comp(a.x * b, a.y * b);
}
inline comp operator / (const comp &a, const db &b) {
return comp(a.x / b, a.y / b);
}
inline comp operator * (const comp &a, const comp &b) {
return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
typedef vector<comp> poly;
inline poly FFT(poly a, int op) {
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
if (i < r[i]) {
swap(a[i], a[r[i]]);
}
}
for (int k = 1; k < n; k <<= 1) {
comp wn(cos(pi / k), sin(pi / k) * op);
for (int i = 0; i < n; i += (k << 1)) {
comp w(1, 0);
for (int j = 0; j < k; ++j, w = w * wn) {
comp x = a[i + j], y = w * a[i + j + k];
a[i + j] = x + y;
a[i + j + k] = x - y;
}
}
}
if (op == -1) {
for (int i = 0; i < n; ++i) {
a[i] = a[i] / n;
}
}
return a;
}
inline poly operator * (poly a, poly b) {
a = FFT(a, 1);
b = FFT(b, 1);
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
a[i] = a[i] * b[i];
}
a = FFT(a, -1);
return a;
}
void solve() {
scanf("%d%d%s%s", &n, &m, s + 1, t + 1);
if (m == 1) {
puts(t[1] == '_' || s[1] == t[1] ? "1" : "0");
return;
}
mp['_'] = 0;
mp['.'] = 1;
int ntot = 1;
for (char c = 'a'; c <= 'z'; ++c) {
mp[c] = ++ntot;
}
for (char c = 'A'; c <= 'Z'; ++c) {
mp[c] = ++ntot;
}
int _n = n;
n = -1;
for (int i = 1; i < m; ++i) {
a[++n] = 1;
}
for (int i = 1; i <= _n; ++i) {
a[++n] = mp[s[i]];
}
for (int i = 1; i < m; ++i) {
a[++n] = 1;
}
--m;
for (int i = 0; i <= m; ++i) {
b[i] = mp[t[i + 1]];
}
int k = 0;
while ((1 << k) <= n + m) {
++k;
}
for (int i = 1; i < (1 << k); ++i) {
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
reverse(b, b + m + 1);
poly A(1 << k), B(1 << k);
for (int i = 0; i <= n; ++i) {
A[i] = comp(a[i] * a[i], 0);
}
for (int i = 0; i <= m; ++i) {
B[i] = comp(b[i], 0);
}
poly C = A * B;
for (int i = m; i <= n; ++i) {
f[i] += C[i].x;
}
A = poly(1 << k);
B = poly(1 << k);
for (int i = 0; i <= n; ++i) {
A[i] = comp(-2 * a[i], 0);
}
for (int i = 0; i <= m; ++i) {
B[i] = comp(b[i] * b[i], 0);
}
C = A * B;
for (int i = m; i <= n; ++i) {
f[i] += C[i].x;
}
ll s = 0;
for (int i = 0; i <= m; ++i) {
s += b[i] * b[i] * b[i];
}
for (int i = m; i <= n; ++i) {
f[i] += s;
}
int ans = 0;
for (int i = m; i <= n; ++i) {
ans += (fabs(f[i]) < 0.4);
}
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}