后缀自动机（Suffix Automaton）原理与构建 后缀自动机（Suffix Automaton, SAM）是一种用于字符串处理的强大数据结构。它能够 接受给定字符串的所有后缀 ，并且其本身是一个 最小的确定性有限状态自动机（DFA） 。其核心优势在于，它仅用O(n)的空间（n是字符串长度），就能在线性时间内构建，并高效支持多种字符串查询，如判断子串、计算不同子串数量、查找所有匹配位置等。 核心概念与定义 状态（State） ：SAM不是简单地将每个前缀或后缀作为一个状态。每个状态代表 一类具有相同“结束位置集合（endpos）”的子串集合 。 结束位置集合（End Positions, endpos） ：对于一个子串s， endpos(s) 定义为s在原字符串S中所有 结束位置 的集合。例如，对于S="abcbc"： endpos("bc") = {3, 5} （"bc"结束于位置3和5）。 endpos("c") = {3, 5} 。 注意"bc"和"c"的 endpos 相同，它们属于SAM中的同一个状态。 后缀链接（Suffix Link, link） ：SAM是一个有向图，除了状态之间的转移边，每个状态还有一个 link 指针，指向另一个状态。如果状态 v 对应 endpos 集合E，那么 link[v] 对应的 endpos 集合是E的一个 真超集 ，并且是满足此条件中 endpos 集合最大的那个状态对应的子串集合。直观上， link[v] 指向的状态代表的是状态 v 所代表的最长子串的 某个最长后缀 ，但这个后缀的 endpos 集合与 v 不同。 构建过程（在线算法，逐字符添加） 我们以构建字符串"ababa"的后缀自动机为例，详细说明每一步。我们用 last 表示当前整个字符串（已添加部分）对应的状态。初始时，只有一个状态0（初始状态）， len[0] = 0 , link[0] = -1 ， last = 0 。 len 表示该状态能代表的 最长 子串的长度。 步骤1：添加字符'a' (S = "a") 创建一个新状态 cur = 1 。 len[cur] = len[last] + 1 = 1 。这个状态代表整个当前字符串"a"。 从状态 last=0 开始，检查是否存在字符'a'的转移。不存在。 因此，我们从状态0添加一条通过'a'到状态 cur=1 的转移边。 现在设置 link[cur] 。我们设一个指针 p = last = 0 。 由于 link[0] = -1 （初始状态没有后缀链接），我们跳出循环。 将 link[cur] 设置为0（因为p最终为-1，这是特例）。 更新 last = cur = 1 。 当前SAM有两个状态：0和1。状态1的 len=1 ， link=0 。它代表子串"a"。 步骤2：添加字符'b' (S = "ab") 创建新状态 cur = 2 。 len[cur] = len[last] + 1 = 2 。代表"ab"。 p = last = 1 。检查状态1是否有字符'b'的转移？没有。因此，从状态1添加一条通过'b'到状态2的转移边。然后 p = link[1] = 0 。 p = 0 。检查状态0是否有字符'b'的转移？没有。因此，从状态0添加一条通过'b'到状态2的转移边。 p = link[0] = -1 ，停止。 设置 link[cur] 。由于p最后为-1，将 link[2] 设置为0。 更新 last = 2 。 状态2代表"ab"， len=2 ， link=0 。 步骤3：添加字符'a' (S = "aba") - 关键步骤，涉及克隆状态 创建新状态 cur = 3 。 len[cur] = 3 。代表"aba"。 p = last = 2 。检查状态2是否有字符'a'的转移？ 没有 。因此，从状态2添加一条通过'a'到状态3的转移边。然后 p = link[2] = 0 。 p = 0 。检查状态0是否有字符'a'的转移？ 有 ！它指向状态1。 设 q 为0通过'a'转移到的状态，即 q = 1 。 现在比较 len[p] + 1 和 len[q] 。 len[0]+1=1 ， len[1]=1 ，两者 相等 。 这种情况下，我们直接将 link[cur] 设置为 q ，即 link[3] = 1 。 然后跳出循环 。 更新 last = 3 。 此时，状态3（"aba"）的 link 指向状态1（"a"）。逻辑是："aba"的最长后缀中， endpos 与"aba"不同的最长者是"a"。 步骤4：添加字符'b' (S = "abab") - 另一个关键步骤，涉及克隆 创建新状态 cur = 4 。 len[cur] = 4 。代表"abab"。 p = last = 3 。检查状态3是否有字符'b'的转移？没有。添加转移 3->b->4 。 p = link[3] = 1 。 p = 1 。检查状态1是否有字符'b'的转移？ 有 ！它指向状态2。 q = 2 。 比较 len[p]+1 和 len[q] 。 len[1]+1=2 ， len[2]=2 ， 相等 。 将 link[cur] 设置为 q ，即 link[4] = 2 。跳出循环。 更新 last = 4 。 步骤5：添加字符'a' (S = "ababa") - 最复杂步骤，需要克隆状态 创建新状态 cur = 5 。 len[cur] = 5 。代表"ababa"。 p = last = 4 。检查状态4是否有字符'a'的转移？没有。添加转移 4->a->5 。 p = link[4] = 2 。 p = 2 。检查状态2是否有字符'a'的转移？ 有 ！它指向状态3。 q = 3 。 关键比较 ： len[p]+1 = 2+1 = 3 ， len[q] = 3 ， 相等 。 看起来应该像上一步一样，直接设置 link[5]=3 并跳出。 但这里有一个陷阱 。我们需要继续检查，因为条件 len[p]+1 == len[q] 是 link 设置的一种情况，但我们需要确保转移的完整性。让我们继续算法描述： 实际上，标准算法在这一步会进行判断。因为我们是从 p=2 通过'a'到达 q=3 ，且 len[2]+1 == len[3] ，按照标准算法，我们 应该 设置 link[5] = 3 然后跳出。 但让我们完整走一遍严格流程： p=2 , 发现转移'a'到 q=3 。 判断 len[p] + 1 == len[q] ? 是的 (3==3)。 因此，设置 link[cur] = q ，即 link[5] = 3 。 跳出循环 。 然而，为了展示 克隆（clone） 这一核心操作，我们需要一个 len[p]+1 < len[q] 的例子。让我们修正一下推理，或者考虑另一个字符串比如"ababc"的最后一步。但为了在当前例子中体现克隆，我们可以设想在步骤3时有所不同。但为了教学完整性，我描述克隆的逻辑： 克隆发生的场景 ：当 p 通过字符 c 转移到 q ，且 len[p] + 1 < len[q] 时。这意味着 q 所代表的最长子串（比如"abx...")的一部分（前缀）是由于我们新加的字符 c 才获得了新的结束位置，而另一部分（更长的部分）早就存在。这时 q 的 endpos 集合将要分裂。 克隆操作 ： 创建一个新状态 clone ，复制 q 的所有转移边和 link 。 设置 len[clone] = len[p] + 1 。 然后，我们将 q 和 cur 的 link 都指向 clone 。 最后，我们将所有从 p 及 p 通过 link 回溯的、原本通过 c 转移到 q 的边，重定向到转移到 clone 。 例如，在字符串"abcabx"的构建中，添加最后的'x'时就可能触发克隆。 在我们的"ababa"例子中，第5步没有触发克隆，最终 link[5]=3 。 更新 last = 5 。 构建完成后的SAM 最终，我们得到了"ababa"的SAM。每个状态代表一组 endpos 相同的子串。例如： 状态5： len=5 , link=3 ，代表{"ababa"}。 状态3： len=3 , link=1 ，代表{"aba"}。 状态4： len=4 , link=2 ，代表{"abab"}。 状态1： len=1 , link=0 ，代表{"a"}。 状态2： len=2 , link=0 ，代表{"ab"}。 状态0： len=0 , link=-1 ，代表空串 ε 。 性质与用途 状态数 ：不超过 2n-1 。 转移数 ：不超过 3n-4 。 判断子串 ：从初始状态0开始，沿着输入子串的字符走，如果能走完，则是原串子串。 不同子串数量 ： sum(len[i] - len[link[i]]) ，对每个状态i求和。因为每个状态i贡献了 (len[i] - len[link[i]]) 个新的、以该状态为终点的 最长 子串（即该状态代表集合中最长的那几个）。 所有子串出现次数 ：可以通过在 link 树上进行DFS，传递子树大小（即 endpos 集合大小）来计算每个状态（子串集合）的出现次数。 总结，后缀自动机通过精妙的 link 指针和在线构建时对状态的复用与克隆，以线性的时间和空间复杂度，压缩存储了一个字符串的所有子串信息，是处理复杂字符串问题的利器。理解 endpos 等价类和 suffix link 构成的树（称为后缀链接树或Parent Tree）是掌握SAM的关键。