后缀自动机 学习笔记

因为 SA 就很有用了，所以一直不想学 SAM。突然不知道为什么就想学了，可能是为了吊打兔兔吧。
后缀自动机 (SAM) 是一个能解决许多字符串相关问题的有力的数据结构。
直观上，SAM 可以理解为将字符串的所有子串高度压缩至理论复杂度下界 $\mathcal O(n)$ 的形式。

确定有限状态自动机 (DFA)

我们先要了解，什么是确定有限状态自动机 (DFA)。

定义

一个 DFA 可以看成一张有向图，由五个部分构成：

1. 状态集合 $Q$：图中的点。
2. 字符集 $\Sigma$：所有合法字符的集合。
3. 转移函数 $\delta(v,c)$：图中的边，其中 $v$ 和返回值都是一个状态，分别对应一条边的起点和终点，$c \in \Sigma$，表示这条边上的字符。
4. 起始状态 $S$：$S \in Q$，是一个特殊的状态。
5. 接受状态集合 $F$：$F \subseteq Q$，是一组特殊的状态。

作用

DFA 可以识别字符串。

当 DFA 读入字符串 $s$ 时，从 $S$ 开始按照 $\delta(v,c)$ 一个一个字符地转移。

特别地，如果某个状态 $v$ 没有字符 $c$ 的转移，则令 $\delta(v,c) = N$，$N$ 只能转移到 $N$，且 $N \notin F$。

如果读入完 $s$ 后处在 $F$ 内，就称这个 DFA 接受 $s$。

扩展定义转移函数 $\delta(v,s)$，其中 $s$ 是一个由 $\Sigma$ 内的字符构成的字符串，则 $\delta(v,s) = \delta(\delta(v,s[1]),s[2:|s|])$。

一个 DFA 是否接受 $s$，等价于求 $[\delta(S, s) \in F]$ 的值。

后缀自动机 (SAM)

后缀自动机 (SAM) 是接受且仅接受字符串 $s$ 的所有后缀的最小 DFA。

构造

$\operatorname{rightpos}$ 等价类

在一些教程中，$\operatorname{rightpos}$ 也被称作 $\operatorname{endpos}$。本文选择 $\operatorname{rightpos}$，是因为同样存在定义类似的 $\operatorname{leftpos}$，而不存在 $\operatorname{beginpos}$ 的叫法。

对于 $s$ 的子串 $t$，记 $\operatorname{rightpos}(t)$ 为 $s$ 中 $t$ 的所有结束（即最右边的字符）位置。如对于字符串 $\texttt{abcbc}$，$\operatorname{rightpos}(\texttt{bc}) = 3,5$。特别地，空串的 $\operatorname{rightpos}$ 定义为 $0,1,\cdots,|s|$。

若两个非空子串 $t_1,t_2$，满足 $\operatorname{rightpos}(t_1) = \operatorname{rightpos}(t_2)$，则将他们划分到一个 $\operatorname{rightpos}$ 等价类中。

SAM 中的每个状态都对应着一个 $\operatorname{rightpos}$ 等价类，其中 $S$ 对应着空串所在的等价类。

$\operatorname{rightpos}$ 性质

• 考虑一个子串 $t$，我们每次去掉 $t$ 的首字母，则它所在的 $\operatorname{rightpos}$ 要么不变，要么会增加若干个新位置。
  形式化地，对于两个子串 $t_1,t_2$，不妨设 $|t_1| \le |t_2|$：
  若 $t_1$ 为 $t_2$ 的后缀，则 $\operatorname{rightpos}(t_2) \subseteq \operatorname{rightpos}(t_1)$；
  否则，说明 $t_2$ 所在的位置 $t_1$ 都不在，即 $\operatorname{rightpos}(t_1) \cap \operatorname{rightpos}(t_2) = \varnothing$。
• 反过来考虑更强一点的性质，如果若干个子串的 $\operatorname{rightpos}$ 一样，意味着它们在 $s$ 中的出现位置一样，且它们一定是由一个子串 $t$ 不断去掉首字母，但还未能增加新位置时的所有子串构成的。
  因此，在一个 $\operatorname{rightpos}$ 等价类中，较短的子串为较长的子串的后缀，且所有子串的长度恰好覆盖一个区间。

后缀链接 $\operatorname{parent}$

对于一个不是 $S$ 的状态 $v$，设它对应的等价类中最短的子串为 $t$。

后缀链接 $\operatorname{parent}(v) = \operatorname{rightpos}(t[2:|t|])$。

另外，对于一个状态 $v$，记 $\operatorname{len}(v)$ 表示它对应的等价类中最长的子串的长度。特别的，$\operatorname{len}(S) = 0$。

$\operatorname{parent}$ 性质

• 依然考虑不断去掉一个子串 $t$ 的首字母：
  如果还未能增加新位置，则还在同一个 $\operatorname{rightpos}$ 等价类中；
  否则，会跳到其 $\operatorname{parent}$ 等价类中。
  因此，对于一个不是 $S$ 的状态 $v$，将其视作 $\operatorname{rightpos}$ 集合，有 $v \subseteq \operatorname{parent}(v)$。
• 根据上条性质，对于一个不是 $S$ 的状态 $v$，它对应的 $\operatorname{rightpos}$ 等价类中，子串的长度区间为 $(\operatorname{len}(\operatorname{parent}(v)), \operatorname{len}(v)]$，即 $v$ 对应的子串数量为 $\operatorname{len}(v) - (\operatorname{len}(\operatorname{parent}(v))$。
• 所有 $\operatorname{parent}$ 构成一棵以 $S$ 为根的树，我们称其为 $\operatorname{parent}$ 树。

构造 SAM

一开始 SAM 只包含一个状态 $S$，编号为 $0$。为了方便，不妨令 $\operatorname{parent}(S) = -1$。

考虑依次添加字符，同时维护每个状态的 $\operatorname{len}$，$\operatorname{parent}$ 和转移。

令 $l$ 表示任意时刻整个字符串对应的状态，每次添加一个字符 $c$ 的过程如下：

1. 创建一个新的状态 $w$，并将 $\operatorname{len}(w)$ 设为 $\operatorname{len}(l) + 1$。
2. 从 $l$ 开始遍历 $\operatorname{parent}$：
   • 如果当前状态不存在字符 $c$ 的转移，则添加一个到 $w$ 的转移。
   • 如果当前状态存在字符 $c$ 的转移，则将这个状态标记为 $p$，转移到的状态标记为 $q$，然后跳出遍历。
3. 接下来有三种情况：
   1. 如果始终没有状态存在字符 $c$ 的转移，则将 $\operatorname{parent}(w)$ 设为 $0$，然后退出。
   2. 否则，若 $\operatorname{len}(p) + 1 = \operatorname{len}(q)$，则将 $\operatorname{parent}(w)$ 设为 $q$，然后退出。
   3. 否则，再创建一个新的状态 $k$，将 $q$ 的 $\operatorname{parent}$ 和转移复制到 $k$ 上，将 $\operatorname{len}(k)$ 设为 $\operatorname{len}(p) + 1$，将 $\operatorname{parent}(w)$ 和 $\operatorname{parent}(q)$ 都设为 $k$。然后从 $p$ 往回遍历 $\operatorname{parent}$，若存在到 $q$ 的转移，则将转移重定向到 $k$ 上。
4. 更新 $l$，即将 $l$ 设为 $w$。

最后，我们再从 $l$ 遍历一次 $\operatorname{parent}$，则 $F$ 即由遍历到的状态构成。

复杂度

如果转移用 map 存储，则时间复杂度为 $\mathcal O(n \log |\Sigma|)$，空间复杂度为 $\mathcal O(n)$。

如果转移用数组存储，同时借助链表，则时间复杂度为 $\mathcal O(n)$，空间复杂度为 $\mathcal O(n |\Sigma|)$。如果不借助链表，时间复杂度为 $\mathcal O(n |\Sigma|)$，空间复杂度为 $\mathcal O(n |\Sigma|)$。

状态数和转移数上界

对于 $|s| \ge 2$ 的字符串，状态数 $\le 2 |s| - 1$，上界可以在 $\texttt{abb}\dots\texttt{b}$ 达到。

对于 $|s| \ge 3$ 的字符串，转移数 $\le 3 |s| - 4$，上界可以在 $\texttt{abb}\dots\texttt{bc}$ 达到。

性质

• $s$ 的子串和 SAM 中从 $S$ 开始的路径一一对应。
  对于一个非 $S$ 状态 $v$，$v$ 对应的 $\operatorname{rightpos}$ 等价类大小 $=$ $v$ 对应的子串数量 $=$ 从 $S$ 开始到 $v$ 的路径数量 $=$ $\operatorname{len}(v) - (\operatorname{len}(\operatorname{parent}(v))$。
• 称 $s$ 的前缀在 SAM 上对应的节点为终点节点。
  对于一个非 $S$ 状态 $v$，$v$ 对应的 $\operatorname{rightpos}$ 集合 $=$ 其 $\operatorname{parent}$ 树的子树内的终点节点所对应前缀的位置 $=$ $v$ 对应的子串在 $s$ 中出现的位置。
  根据此条性质，我们可以方便地采用线段树合并求出 $\operatorname{rightpos}$ 集合。
• 说白了，SAM 中的概念，包括 $\operatorname{rightpos}$、$\operatorname{parent}$、终点节点、前缀、后缀、子串、路径，全都能串起来。
  串起来之后，随便组合就有各种各样的性质。
  例如，$s$ 的任意两个前缀对应的终点节点在 $\operatorname{parent}$ 树上的 LCA 所对应的最长子串就是这两个前缀的最长公共后缀。

应用

【模板】P3804 【模板】后缀自动机 (SAM)

根据：

• 对于一个非 $S$ 状态 $v$，$v$ 对应的 $\operatorname{rightpos}$ 集合 $=$ 其 $\operatorname{parent}$ 树的子树内的终点节点所对应前缀的位置 $=$ $v$ 对应的子串在 $s$ 中出现的位置。

每个前缀所在的状态有贡献 $1$。

那么，对每个状态求出其 $\operatorname{parent}$ 树上的子树贡献和，然后乘上这个状态的 $\operatorname{len}$，最后取 $\max$ 即可。

const int N = 1e6 + 7;
struct SAM {
	int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
	char s[N];
	inline void init() { pa[0] = -1; }
	inline void add(int c) {
		int w = ++t, p = l;
		len[w] = len[l] + 1;
		while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
		if (!~p) return pa[l=w] = 0, void();
		int q = ch[p][c];
		if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
		int k = ++t;
		pa[k] = pa[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
		len[k] = len[p] + 1, pa[w] = pa[q] = k;
		while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
		l = w;
	}
	inline void build() {
		init();
		for (int i = 1; i <= n; i++) add(s[i] - 'a');
	}

	int cnt[N<<1];
	ll ans;
	vi e[N<<1];
	void dfs(int x) {
		for (int y : e[x]) dfs(y), cnt[x] += cnt[y];
		if (cnt[x] > 1) ans = max(ans, 1ll * cnt[x] * len[x]);
	}
	inline void calc() {
		for (int i = 1, p = 0; i <= n; i++) p = ch[p][s[i]-'a'], ++cnt[p];
		for (int i = 1; i <= t; i++) e[pa[i]].pb(i);
		dfs(0), print(ans);
	}
} sam;

int main() {
	rds(sam.s, sam.n);
	sam.build(), sam.calc();
	return 0;
}

【例题】P4070 [SDOI2016]生成魔咒

动态子串数。

每加入一个字符，本质不同的子串数就会加 $\operatorname{len}(l) - \operatorname{len}(\operatorname{parent}(k))$ 个。

【例题】SP7258 SUBLEX - Lexicographical Substring Search

第 $k$ 小子串。

由于 SAM 是个 DAG，因此设 $cnt_i$ 表示从 $i$ 开始的路径条数，拓扑排序后再 DAG 上 dp。

这里拓扑排序可以利用基数排序，借助转移一定是从 $\operatorname{len}$ 小的往大的即可。

找答案时，从根开始贪心地找。

const int N = 9e4 + 7;
struct SAM {
	int n, l, len[N<<1], pa[N<<1], t;
	char s[N];
	map<char, int> ch[N<<1];
	inline void init() { pa[0] = -1; }
	inline void add(char c) {
		int w = ++t, p = l;
		len[w] = len[l] + 1;
		while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
		if (!~p) return pa[l=w] = 0, void();
		int q = ch[p][c];
		if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
		int k = ++t;
		pa[k] = pa[q], ch[k] = ch[q];
		len[k] = len[p] + 1, pa[w] = pa[q] = k;
		while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
		l = w;
	}
	inline void build() {
		init();
		for (int i = 1; i <= n; i++) add(s[i]);
	}

	int b[N<<1], c[N];
	ll cnt[N<<1];
	inline void sort() {
		for (int i = 1; i <= t; i++) ++c[len[i]];
		for (int i = 1; i <= n; i++) c[i] += c[i-1];
		for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
		for (int i = t; ~i; i--) {
			int x = b[i];
			cnt[x] = 1;
			for (auto o : ch[x]) cnt[x] += cnt[o.se];
		}
	}
	inline void ask(int x) {
		int p = 0;
		while (x)
			for (auto o : ch[p])
				if (x - cnt[o.se] > 0) x -= cnt[o.se];
				else {
					putchar(o.fi), p = o.se, --x;
					break;
				}
		putchar('\n');
	}
} sam;

int main() {
	rds(sam.s, sam.n), sam.build(), sam.sort();
	int q, x;
	rd(q);
	while (q--) rd(x), sam.ask(x);
	return 0;
}

【例题】SP1811 LCS - Longest Common Substring

两个串的最大公共子串。

对第一个串建 SAM，然后依次加入第二个串的字符，求当前第二个串的是第一个串的子串的最长后缀。

用一个指针记录当前解在 SAM 上的位置，加入一个字符时先看能不能匹配，如果能就直接匹配，不能就暴力跳 $\operatorname{parent}$，直到可以匹配为止。

每次的解取 $\max$ 即为最优解。

const int N = 2.5e5 + 7;
struct SAM {
	int n, l, len[N<<1], pa[N<<1], t;
	char s[N];
	map<char, int> ch[N<<1];
	inline void init() { pa[0] = -1; }
	inline void add(char c) {
		int w = ++t, p = l;
		len[w] = len[l] + 1;
		while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
		if (!~p) return pa[l=w] = 0, void();
		int q = ch[p][c];
		if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
		int k = ++t;
		pa[k] = pa[q], ch[k] = ch[q];
		len[k] = len[p] + 1, pa[w] = pa[q] = k;
		while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
		l = w;
	}
	inline void build() {
		init();
		for (int i = 1; i <= n; i++) add(s[i]);
	}

	int op, ol, ans;
	inline void calc(char c) {
		while (op && !ch[op][c]) op = pa[op], ol = len[op];
		if (ch[op][c]) op = ch[op][c], ++ol;
		ans = max(ans, ol);
	}
} sam;

char s[N];
int n;

int main() {
	rds(sam.s, sam.n), sam.build();
	rds(s, n);
	for (int i = 1; i <= n; i++) sam.calc(s[i]);
	print(sam.ans);
	return 0;
}

【例题】SP10570 LONGCS - Longest Common Substring

多个串的最大公共子串。

依然对第一个串建 SAM，类似两个串的情况，将其他串放到 SAM 上匹配。

维护 SAM 每个状态的最长匹配长度，每次的解取 $\min$，所有状态取 $\max$ 即可。

const int N = 1e4 + 7;
char s[N];
int n, ans[N<<1];
struct SAM {
	int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
	char s[N];
	inline void init() {
		for (int i = 0; i <= t; i++)
			memset(ch[i], 0, sizeof(ch[i]));
		t = l = len[0] = 0, pa[0] = -1;
	}
	inline void add(int c) {
		int w = ++t, p = l;
		len[w] = len[l] + 1;
		while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
		if (!~p) return pa[l=w] = 0, void();
		int q = ch[p][c];
		if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
		int k = ++t;
		pa[k] = pa[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
		len[k] = len[p] + 1, pa[w] = pa[q] = k;
		while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
		l = w;
	}
	inline void build() {
		init();
		for (int i = 1; i <= n; i++) add(s[i] - 'a');
	}

	int b[N<<1], c[N];
	inline void sort() {
		for (int i = 1; i <= n; i++) c[i] = 0;
		for (int i = 1; i <= t; i++) ++c[len[i]];
		for (int i = 1; i <= n; i++) c[i] += c[i-1];
		for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
	}
	int op, ol, ans[N<<1];
	inline void calc(int c) {
		while (op && !ch[op][c]) op = pa[op], ol = len[op];
		if (ch[op][c]) op = ch[op][c], ++ol, ans[op] = max(ans[op], ol);
	}
	inline void update() {
		for (int i = t; i; i--) {
			int x = b[i];
			ans[pa[x]] = max(ans[pa[x]], min(ans[x], len[pa[x]]));
			::ans[x] = min(::ans[x], ans[x]), ans[x] = 0;
		}
	}
} sam;

inline void solve() {
	int m;
	rd(m), rds(sam.s, sam.n), sam.build(), sam.sort();
	for (int i = 1; i <= sam.t; i++) ans[i] = 1e9;
	while (--m) {
		rds(s, n), sam.op = sam.ol = 0;
		for (int i = 1; i <= n; i++) sam.calc(s[i] - 'a');
		sam.update();
	}
	print(*max_element(ans + 1, ans + sam.t + 1));
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

参考资料

• OI Wiki 后缀自动机 (SAM)
• OI Wiki 自动机
• EternalAlexander 炫酷后缀树魔术
• 张天扬 后缀自动机及其应用
• 吴作同 后缀自动机的理解与运用