P4173 残缺的字符串 题解

P4173 残缺的字符串

带通配符的字符串匹配模板题。

两个长度为 $n$ 的字符串 $a, b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2 = 0$。

如果带有通配符，将通配符看成 $0$，则 $a,b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2a_ib_i = 0$。

套路地将 $a$ 串翻转，则 $a,b$ 相等当且仅当： $$\begin{aligned} \sum_{i=1}^n (a_i-b_{n+1-i})^2a_ib_{n+1-i} &= 0 \\\\ \sum_{i=1}^n (a_i^2-2a_ib_{n+1-i}+b_{n+1-i}^2)a_ib_{n+1-i} &= 0 \\\\ \sum_{i=1}^n a_i^3b_{n+1-i} - \sum_{i=1}^n 2a_i^2b_{n+1-i}^2 + \sum_{i=1}^n a_ib_{n+1-i}^3 &= 0 \\\\ \end{aligned}$$ 最后即为三个卷积，可以 $\mathcal O(n \log n)$ 判断。

回到本题，首先翻转 $a$ 串，设 $f(p) = \sum_{i=1}^n a_i^3b_{n+p-i} - \sum_{i=1}^n 2a_i^2b_{n+p-i}^2 + \sum_{i=1}^n a_ib_{n+p-i}^3$。

则 $f(p) = 0$ 的 $p$ 即为合法的位置。

个人喜欢用 NTT，因为没有精度问题。当然会有冲突，但相当于 Hash，除了 CF 一般不会被卡。

namespace NTT {
	const int N = 1 << 21 | 1;
	int n, m, k, l, r[N];
	modint vk, g = 3, vg = 332748118, a[N], b[N];
	inline void ntt(modint *a, int n, int x) {
		for (int i = 0; i < n; i++) if (i < r[i]) swap(a[i], a[r[i]]);
		for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) {
			modint W = (x > 0 ? g : vg) ^ ((P - 1) / o);
			for (int i = 0; i < n; i += o) {
				modint w = 1;
				for (int j = 0; j < k; j++, w *= W)
					a[i+j+k] *= w,
					a[i+j] += a[i+j+k],
					a[i+j+k] = a[i+j] - a[i+j+k] - a[i+j+k];
			}
		}
	}
	inline void solve() {
		k = 1, l = 0;
		while (k <= n + m) k <<= 1, ++l;
		vk = (modint)1 / k;
		for (int i = 0; i < k; i++)
			r[i] = (r[i>>1] >> 1) | ((i & 1) << (l - 1));
		for (int i = n + 1; i < k; i++) a[i] = 0;
		for (int i = m + 1; i < k; i++) b[i] = 0;
		ntt(a, k, 1), ntt(b, k, 1);
		for (int i = 0; i < k; i++) a[i] *= b[i];
		ntt(a, k, -1);
		for (int i = 0; i <= n + m; i++) a[i] *= vk;
	}
}

const int N = 3e5 + 7;
int n, m;
char a[N], b[N];
modint f[N];

int main() {
	rd(n, m), rds(a, n), rds(b, m);
	reverse(a + 1, a + n + 1);
	NTT::n = n, NTT::m = m;
	for (int i = 1; i <= n; i++)
		if (a[i] == '*') a[i] = 0;
	for (int i = 1; i <= m; i++)
		if (b[i] == '*') b[i] = 0;
	
	for (int i = 1; i <= n; i++)
		NTT::a[i] = a[i] * a[i] * a[i];
	for (int i = 1; i <= m; i++)
		NTT::b[i] = b[i];
	NTT::solve();
	for (int p = 1; p + n - 1 <= m; p++)
		f[p] += NTT::a[p+n];
	
	for (int i = 1; i <= n; i++)
		NTT::a[i] = a[i] * a[i];
	for (int i = 1; i <= m; i++)
		NTT::b[i] = b[i] * b[i];
	NTT::solve();
	for (int p = 1; p + n - 1 <= m; p++)
		f[p] -= 2 * NTT::a[p+n];
	
	for (int i = 1; i <= n; i++)
		NTT::a[i] = a[i];
	for (int i = 1; i <= m; i++)
		NTT::b[i] = b[i] * b[i] * b[i];
	NTT::solve();
	for (int p = 1; p + n - 1 <= m; p++)
		f[p] += NTT::a[p+n];
	
	vi ans;
	for (int p = 1; p + n - 1 <= m; p++)
		if (!f[p]) ans.pb(p);
	print(ans.size());
	for (int x : ans) print(x, ' ');
	return 0;
}