526互联

AtCoder Beginner Contest 307 Ex Marquee

发布时间 2023-06-26 20:25:41作者: zltzlt

洛谷传送门

AtCoder 传送门

一开始看错题了，看了好久才发现就是个板子。。。

这个东西本质上是循环移位，我们考虑在 \(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;
}