「Wallace 笔记」序列自动机 简单入门

基本概念

记号

同为 DFA 的记号。

  • (Sigma)：字符集；
  • (Q)：状态集；
  • (q_0(in Q))：起始状态；
  • (F(in Q))：接受状态集；
  • (delta)：转移函数。
    • (delta(x, c)) 表示状态 (x) 的字符 (c) 的转移。若无记为 ( ext{null})
    • (delta(x, S)) 其中 (S) 为字符串，等价于 (delta(delta(x, S[1, |S| - 1]), S_{|S|}))

定义

序列自动机是接受且仅接受一个字符串的子序列的自动机。

如当 (Sigma = { exttt{a, b, c} })，(S = exttt{abac}) 时，其序列自动机为：

Udi5bd.png

状态

对字符串 (S) 构建序列自动机，那么这个自动机中存在 (|S| + 1) 个状态。

对于字符串 (T)，状态 (delta(q_0, T)) 表示 (T) 作为 (S) 的子序列，在 (S) 中第一次出现的末端位置。

若 (delta(q_0, T) = ext{null})，则说明 (T) 不是 (S) 的子序列。

根据定义，序列自动机上的所有状态都是接受状态（(F = Q)）。

转移函数

转移函数 (delta) 的设计，我们可以贪心地认为 (delta(x, c)) 就是 字符串中位置 (x) 之后，字符 (c) 下一次的出现位置。

但很显然之后可能会有多个 (c)，为什么选取最前面的呢？假如说 (i < j)，那么后缀 (S[j, |S|]) 中的所有子序列一定被完全包含在后缀 (S[i, |S|]) 中。换句话说，(S[j, |S|]) 的所有子序列的集合为 (S[i, |S|]) 所有子序列的子集。于是不难发现后面的一定不会优于前面。

形式化地讲，(delta(x, c) = min{ y | S_y = c, y > x })。如果不存在不妨设为 (-1) 表示 ( ext{null})。

构造算法

朴素算法

首先，根据上文对转移函数的讨论，我们可以从后往前扫，逐位构建。

对于状态 (i)，假如已经求出了 (delta(i, c)) 的转移，考虑如何推出状态 (i - 1) 的转移函数。

不难发现，只有一个位置，即 (S_i) 的值的位置上，是需要变动的，那么：(delta(i - 1, S_i) = i)。

其他字符的转移，只需要直接复制下来即可。这样的算法的时空复杂度为 (O(|S| imes |Sigma|))。

代码非常简单：

for (register int i = 1; i <= m; i++) // 最后一位的所有转移置为 null
	next[n][i] = -1;
for (register int i = n; i; i--) { // 倒序逐位构造
	for (register int j = 1; j <= m; j++) // 先复制前一轮的结果
		next[i - 1][j] = next[i][j];
	next[i - 1][dat[i]] = i; // 更新当前字符的转移
}

可持久化数组优化

上一个算法的效率在 (Sigma) 大小过大时都不够优秀，问题在于对前面状态复制了过多信息。

然而我们只需要改变一个位置的值，把整个赋值显然是浪费。

这就需要 可持久化 的思想了——我们先对最后一个建出线段树，初始值为 (-1)。

接下来在构建时只需在一个位置更新即可。时空复杂度 (O(|S|log |Sigma|))。较之前都有较大的提高。

struct segt_node {
	segt_node* lc;
	segt_node* rc;
	int l, r, val;
	
	#define mid ((this->l + this->r) >> 1)
	segt_node(segt_node *last, int pos, int _val) : l(last->l), r(last->r), val(0) {
		if (this->l == this->r) { val = _val; return; }
		if (pos <= mid) {
			rc = last->rc;
			lc = new segt_node(last->lc, pos, _val);
		} else {
			lc = last->lc;
			rc = new segt_node(last->rc, pos, _val);
		}
	}
	segt_node(int L, int R) : l(L), r(R), val(-1) {
		if (l == r) return;
		lc = new segt_node(l, mid);
		rc = new segt_node(mid + 1, r);
	}
	int at(int pos) {
		if (this->l == this->r) return this->val;
		if (pos <= mid) return this->lc->at(pos);
		else return this->rc->at(pos);
	}
	#undef mid
} *root[N];

// main 函数内：
	root[n] = new segt_node(1, m);
	for (register int i = n; i; --i)
		root[i - 1] = new segt_node(root[i], dat[i], i);

二分查找（非显式构建）

其实还有一种不需要显式构造出的方法。我们建出自动机，实际上就是需要快速计算出转移函数 (delta)。

但假如我们并没有构造出自动机，不过仍能高效得到转移函数的值，好像并不是不可以。

这里就有一种非常方便的方法：二分查找。

我们先预处理出 (Sigma) 中每一种值的出现位置，这一可以用 vector 实现。为方便讨论，记 (p(i)) 为字符 (i) 在字符串中的出现位置的集合。

在做转移时，假设要得到 (delta(x - 1, c))，那么只要 找出集合 (p(c)) 中第一个 (ge c) 的元素。

由于我们预处理 (p) 集合时就是自然有序的，因此只需要二分查找即可（upper_bound）。

这样的空间可以达到 (O(|S|))。

习题

后记

reference：

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/-Wallace-/p/13297178.html