Luogu4173 残缺的字符串

博主： tony102
发布时间：2021 年 06 月 22 日
956 次浏览
暂无评论
1405字数
分类：题解

[Link](https://www.luogu.com.cn/problem/P4173)

## Sol

学马老师的多项式做法. 字符串里的 `*` 就是通配符. 默认下标全部从 $0$ 开始

首先, 能够匹配的文本串的一个连续子串要满足的条件我们可以写出: $\forall j \in [0,m), \exists i \in [0,n -m)$, 有 $a_j = b_{i+j} || a_j = * || b_{i+j} = *$

式子非常好理解,就跟 `if` 语句一样. 其中 `||` 就是逻辑或运算.

那我们多项式 $f(x)$, 有 $if. a_i = *, f(x) = 0$. 若 $a_i$ 是一个小写字母, 那我们就令 $f(x) = a_i - 'a' + 1$

将逻辑或运算视作乘法, $\forall$ 条件视作加法. 两个字符$(a_x,b_y)$ 可以匹配等价于:

$$
[f(x) \times f(y) \times (f(x) - f(y)) ^ 2] = 0
$$

那么一个模式串都能匹配就是:

$$
\sum_{j=0}^{m-1} f(a_j) \times f(b_{i+j}) \times (f(a_j) - f(b_{i+1})^2) = 0
$$

考虑怎么变成一个卷积的形式. 把 $a$ 倒过来求和, 也就是令 $a' = a_{n-i-1}$. 上式变为:

$$
\sum_{j=0}^{m-1} f(a'_{n-j-1}) \times f(b_{i+j}) \times (f(a'_{n-j-1}) - f(b_{i+1})^2) = 0
$$

拆开之后就是 (令 $A = a'_{n-i-1}, B = b_{i+j}$)

$$
\sum_{j=0}^{m-1} f^3(A)f(B) - 2f^2(A)f^2(B) + f(A)f^3(B) = 0
$$

做三次乘法即可. 每次出答案的时候可以先不 IDFT 回来,最后一起 IDFT, 可以省两次.

## Code

看讨论有人说出题人卡 `998244353` 的模数,我感觉没有, 但是我还是换了一个

有人说还是过不去, 有大法可以随机给小写字母的对应的系数赋值. 我感觉这样是没问题的

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 4e6 + 5;
const LL mod = 1004535809, G = 3;

int n, m;
int a[SIZE], b[SIZE]; LL f[SIZE], g[SIZE], h[SIZE], Gi;
char tmp[SIZE], txt[SIZE];

namespace GTR {
	inline int read() {
		int a = 0, b = 1, c = getchar();
		while (c < 48 || c > 57) b ^= c == '-', c = getchar();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = getchar();
		return b ? a : -a;
	}
} using GTR::read;

LL qPow(LL a, LL b) {
	LL ans = 1ll;
	for ( ; b; b >>= 1, a = a * a % mod) {
		if (b & 1) ans = ans * a % mod;
	}
	return ans % mod;
}

namespace poly {
	int len = 0, N = 1, M = 2, pos[SIZE << 1];

void init(int l) {
		N = 1, M = l, len = 0;
		for ( ; N <= M; N <<= 1, ++ len);
		for (int i = 0; i < N; ++ i) pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1)));
	}

void NTT(LL *a, int opt) {
		LL t, wn, w, *a0, *a1;
		for (int i = 0; i < N; ++ i) if (i < pos[i]) std::swap(a[i], a[pos[i]]);
		for (int i = 1, j, k; i < N; i <<= 1) 
			for (wn = qPow(opt == 1 ? G : Gi, (mod - 1) / (i << 1)), j = 0; j < N; j += (i << 1))
				for (w = 1ll, k = 0ll, a1 = i + (a0 = a + j); k < i; ++ k, ++ a0, ++ a1, (w *= wn) %= mod) 
					t = *a1 * w % mod, *a1 = (*a0 - t + mod) % mod, (*a0 += t) %= mod;
		if (opt == 1) return;
		LL iv = qPow(N, mod - 2);
		for (int i = 0; i < N; ++ i) a[i] = a[i] * iv % mod;
	}
}
#define rev (n - i - 1)

int main() {
	n = read(), m = read(); Gi = qPow(G, mod - 2);
	scanf("%s", tmp); scanf("%s", txt);
	for (int i = 0; i < n; ++ i) a[i] = tmp[rev] == '*' ? 0 : tmp[rev] - 'a' + 1;
	for (int i = 0; i < m; ++ i) b[i] = txt[i] == '*' ? 0 : txt[i] - 'a' + 1;
	poly::init(n + m); int N = poly::N;
	for (int i = 0; i < N; ++ i) f[i] = a[i] * a[i] * a[i], g[i] = b[i];
	poly::NTT(f, 1), poly::NTT(g, 1);
	for (int i = 0; i < N; ++ i) h[i] = f[i] * g[i] % mod, f[i] = 2ll * a[i] * a[i], g[i] = b[i] * b[i];
	poly::NTT(f, 1), poly::NTT(g, 1);
	for (int i = 0; i < N; ++ i)
		h[i] = (h[i] - (f[i] * g[i] % mod) + mod) % mod, f[i] = a[i], g[i] = b[i] * b[i] * b[i];
	poly::NTT(f, 1), poly::NTT(g, 1);
	for (int i = 0; i < N; ++ i) h[i] = (h[i] + f[i] * g[i] % mod) % mod;
	poly::NTT(h, -1);
	std::vector < LL > ans; ans.clear();
	for (int i = n - 1; i <= m - 1; ++ i) {
		if (h[i] == 0) ans.emplace_back(i + 2 - n);
	}
	if (ans.size() > 0) {
		printf("%d\n", ans.size());
		for (auto it: ans) printf("%lld ", it);
		puts("");
	}
	else puts("0");
	return 0;
}
```

最后修改：2021 年 09 月 07 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

CJ_S00021
我是真的zhouhaoxu，声明一下我不是张清的，我是他的npy。
CJ_zhouhaoxu
我是真的S00021，说两句，第一，我是张青的星怒；第二，第一...
看透一切的大黄
⌇●﹏●⌇
观月
受益匪浅
Harkerbest
好好好

Luogu4173 残缺的字符串

tony102 • 2021 年 06 月 22 日

[Link](https://www.luogu.com.cn/problem/P4173)

## Sol

学马老师的多项式做法. 字符串里的 `*` 就是通配符. 默认下标全部从 $0$ 开始

首先, 能够匹配的文本串的一个连续子串要满足的条件我们可以写出: $\forall j \in [0,m), \exists i \in [0,n -m)$, 有 $a_j = b_{i+j} || a_j = * || b_{i+j} = *$

式子非常好理解,就跟 `if` 语句一样. 其中 `||` 就是逻辑或运算.

那我们多项式 $f(x)$, 有 $if. a_i = *, f(x) = 0$. 若 $a_i$ 是一个小写字母, 那我们就令 $f(x) = a_i - 'a' + 1$

将逻辑或运算视作乘法, $\forall$ 条件视作加法. 两个字符$(a_x,b_y)$ 可以匹配等价于:

$$
[f(x) \times f(y) \times (f(x) - f(y)) ^ 2] = 0
$$

那么一个模式串都能匹配就是:

$$
\sum_{j=0}^{m-1} f(a_j) \times f(b_{i+j}) \times (f(a_j) - f(b_{i+1})^2) = 0
$$

考虑怎么变成一个卷积的形式. 把 $a$ 倒过来求和, 也就是令 $a' = a_{n-i-1}$. 上式变为:

$$
\sum_{j=0}^{m-1} f(a'_{n-j-1}) \times f(b_{i+j}) \times (f(a'_{n-j-1}) - f(b_{i+1})^2) = 0
$$

拆开之后就是 (令 $A = a'_{n-i-1}, B = b_{i+j}$)

$$
\sum_{j=0}^{m-1} f^3(A)f(B) - 2f^2(A)f^2(B) + f(A)f^3(B) = 0
$$

做三次乘法即可. 每次出答案的时候可以先不 IDFT 回来,最后一起 IDFT, 可以省两次.

## Code

看讨论有人说出题人卡 `998244353` 的模数,我感觉没有, 但是我还是换了一个

有人说还是过不去, 有大法可以随机给小写字母的对应的系数赋值. 我感觉这样是没问题的

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 4e6 + 5;
const LL mod = 1004535809, G = 3;

int n, m;
int a[SIZE], b[SIZE]; LL f[SIZE], g[SIZE], h[SIZE], Gi;
char tmp[SIZE], txt[SIZE];

LL qPow(LL a, LL b) {
	LL ans = 1ll;
	for ( ; b; b >>= 1, a = a * a % mod) {
		if (b & 1) ans = ans * a % mod;
	}
	return ans % mod;
}

namespace poly {
	int len = 0, N = 1, M = 2, pos[SIZE << 1];

void init(int l) {
		N = 1, M = l, len = 0;
		for ( ; N <= M; N <<= 1, ++ len);
		for (int i = 0; i < N; ++ i) pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1)));
	}

Luogu4173 残缺的字符串

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

Luogu5341 [TJOI2019]甲苯先生和大中锋的字符串

Luogu1891 疯狂 LCM

Indoor Gaussian Splatting Paper Report 1

20211115 月 (yaya)

ARC124D Yet Another Sorting Problem

Luogu4173 残缺的字符串

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Luogu4173 残缺的字符串

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款