字符串算法：后缀自动机 (SAM) 简介

什么是后缀自动机 (SAM)？

后缀自动机（Suffix Automaton, SAM）是一个强大而精巧的数据结构，它能接受一个字符串 S 的所有后缀。更神奇的是，它实际上也接受了 S 的 所有子串。SAM 是一个既包含字符串所有子串信息，又具有最小节点和边数的有向无环图（DAG）。

对于一个长度为 n 的字符串，SAM 的空间复杂度和在线构建的时间复杂度都是线性的 O(n)。

核心概念

1. 状态 (State): SAM 中的每个节点代表一个状态，每个状态对应着原字符串中一个或多个子串的集合。
2. 转移 (Transition): 状态之间的有向边代表字符的转移。从状态 u 到 v 有一条字符 c 的转移边，表示在 u 所代表的子串集合中的所有字符串末尾添加字符 c 后，得到的新字符串都属于 v 所代表的子串集合。
3. 后缀链接 (Suffix Link): 这是 SAM 最核心的概念之一。每��非初始状态都有一个后缀链接，指向另一个状态。状态 u 的后缀链接指向状态 v，表示 v 所代表的子串集合是 u 所代表的子串集合中 所有字符串 的 最长后缀，且这些后缀也存在于 v 的子串集合中。所有后缀链接最终都会指向初始状态，形成一棵树状结构（Parent Tree）。

SAM 的性质

• SAM 是一个 DAG，状态数和转移数都是线性的。
• 从初始状态出发的任意一条路径，都对应着原字符串的一个子串。
• 一个字符串是 S 的子串，当且仅当它能被 SAM 接受。
• 在 Parent Tree 上，一个节点的祖先节点们代表了该节点所有子串的后缀。

构建算法

SAM 的构建是一个在线算法，即逐个添加字符串的字符来构建。假设我们已经为字符串 S 构建好了 SAM，现在要添加一个新字符 c 形成 Sc。

构建过程大致如下：

1. 创建一个新状态 cur 代表整个新串 Sc。
2. 找到代表旧串 S 的状态 last。
3. 从 last 开始，沿着后缀链接往回跳。如果当前节点没有字符 c 的转移，就添加一条到 cur 的转移。
4. 如果跳回到了初始状态，说明字符 c 从未出现过，cur 的后缀链接直接指向初始状态。
5. 如果在某个节点 p 找到���字符 c 的转移，指向状态 q，情况会变得复杂：
   • 如果 len[q] == len[p] + 1，说明 q 对应的最长串就是 p 后面接个 c，是 Sc 的一个后缀。直接将 cur 的后缀链接指向 q 即可。
   • 否则，情况最复杂。这意味着 q 不仅代表了 Sc 的后缀，还代表了其他更长的、不是 Sc 后缀的子串。此时需要“分裂”状态 q：创建一个新的克隆状态 clone，复制 q 的信息，但 len[clone] 设为 len[p] + 1。然后将 q 和 cur 的后缀链接都指向 clone，并重定向一些旧的转移到 clone 上。

应用

SAM 在字符串问题中应用极其广泛，例如：

• 检查一个串是否是另一个串的子串。
• 计算不同子串的数量。
• 计算所有子串的总长度。
• 字典序第 k 大子串。

掌握 SAM 需要对字符串和自动机有较深的理解，但它无疑是解决子串相关问题的最强工具之一。