序列自动机

浅谈序列自动机

link

序列自动机是淦什么的

序列自动机好高级的名字用于解决子序列问题，可以在线性时间判断串 $T$ 是否是串 $S$ 的子序列，这篇文章主要介绍两种方法实现。

做法 1

我们求出一个数组 $f_{i,c}$ 表示在模式串 $S$ 中位置 $i$ 后字符 $c$ 第一次出现的位置。这个很简单，我们倒序枚举 $S$，从 $i + 1$ 继承值并更新。

for (int i = 1; i <= m; i ++) f[n][i] = -1; // m 是字符范围
for (int i = n - 1; i >= 0; i --) {
	for (int j = 1; j <= m; j ++) f[i][j] = f[i + 1][j];
	f[i][s[i + 1]] = i + 1;
}

然后我们要用这个东西判断 $T$ 是否是 $S$ 的子序列。考虑贪心，我们枚举 $T$ 的字符一个一个做过去，现在枚举到的字符在 $S$ 中多次出现，显然选择最靠前的最优，因为这样留给后面的选择空间跟多。所以可以得到判断的代码：

int len = read(), flag = 1, now = 0;
for (int i = 1; i <= len; i ++) {
	int x = read();
	if (flag) {
		if (!(~f[now][x])) flag = 0;
		else now = f[now][x];
	}
}

这样做的空间复杂度是 $\Theta(nm)$，$n$ 为模式串长度，$m$ 为字符集大小，时间复杂度为 $\Theta(nm + n)$。预处理以及空间复杂度在字符集的数量级和 $n​$ 相同时过大，如下代码：

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

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define N 100010
#define M 30

int n, q, m, s[N], f[N][M];

int main() {
	n = read(), n = read(), q = read(), m = read();
	for (int i = 1; i <= n; i ++) s[i] = read();

	for (int i = 1; i <= m; i ++) f[n][i] = -1;
	for (int i = n - 1; i >= 0; i --) {
		for (int j = 1; j <= m; j ++) f[i][j] = f[i + 1][j];
		f[i][s[i + 1]] = i + 1;
	}

	while (q --) {
		int len = read(), flag = 1, now = 0;
		for (int i = 1; i <= len; i ++) {
			int x = read();
			if (flag) {
				if (!(~f[now][x])) flag = 0;
				else now = f[now][x];
			}
		}
		(flag) ? puts("Yes") : puts("No");
	}
	return 0;
}

在模板题中只过了第二个 subtask /jk。

死相极其惨烈。

做法 2

我们开 $m$ 个 $\tt{vector}$，记录字符 $c$ 的所有出现位置。

for (int i = 1; i <= n; i ++) v[read()].pb(i);

每次判断时，我们使用和做法 1 相同的贪心，但是我们改用二分在 $\tt{vector}$ 查找。

for (int i = 1; i <= len; i ++) {
	int x = read();
	if (flag) {
		auto t = lower_bound(v[x].begin(), v[x].end(), now + 1);
		if (t == v[x].end()) flag = 0;
		else now = v[x][t - v[x].begin()];
	}
}

这种方法空间复杂度 $\Theta(n)$，时间复杂度 $\Theta(n \log n)$。

完整代码：

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

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define N 100010
#define pb push_back

int n, m, q;
vector<int> v[N];

int main() {
	n = read(), n = read(), q = read(), m = read();
	for (int i = 1; i <= n; i ++) v[read()].pb(i);
	while (q --) {
		int len = read(), flag = 1, now = 0;
		for (int i = 1; i <= len; i ++) {
			int x = read();
			if (flag) {
				auto t = lower_bound(v[x].begin(), v[x].end(), now + 1);
				if (t == v[x].end()) flag = 0;
				else now = v[x][t - v[x].begin()];
			}
		}
		(flag) ? puts("Yes") : puts("No");
	}
	return 0;
}