后缀自动机（Suffix Automaton）的应用：最长重复子串与最小表示法

字数 3560 2025-12-14 11:12:37

后缀自动机（Suffix Automaton）的应用：最长重复子串与最小表示法

描述
后缀自动机（SAM）是一种强大的数据结构，能在线性时间内构建出一个字符串的所有后缀的压缩表示。它不仅支持许多字符串查询（如子串出现次数、最长公共子串等），还能解决一些更复杂的问题。本次专题聚焦于两个经典应用：

最长重复子串：在一个字符串中找到一个长度最大的子串，该子串在字符串中至少出现两次（允许重叠）。
最小表示法：对于一个循环同构的字符串集合（如字符串的循环移位），找到字典序最小的那个表示。

理解这些应用能加深对SAM本质（状态转移、link指针、len性质）的掌握，并体会其在字符串处理中的通用性。

解题过程详解

一、回顾后缀自动机（SAM）的核心性质

在讲解应用前，我们先快速回顾SAM的关键点（假设已了解SAM基本构建，这里不重复状态转移函数next、后缀链接link、状态最大长度len等定义）：

SAM的状态数不超过2n-1，转移数不超过3n-4（n为字符串长度）。
每个状态对应一个**endpos等价类**，即子串结束位置的集合。
从初始状态出发，沿转移走出的每条路径对应原字符串的一个子串。
状态u对应的所有子串长度连续，区间为[len(link(u))+1, len(u)]。
沿着link指针向上走，相当于不断缩短当前子串（去掉首字符），形成后缀关系。

二、应用1：最长重复子串

问题：给定字符串s，求最长的子串，使得它在s中出现至少两次（出现位置可重叠）。

思路分析

重复子串意味着存在至少两个不同的起始位置i和j，使得s[i:i+L] = s[j:j+L]。
在SAM中，一个子串对应从初始状态到达某个状态的某条路径。
如果子串出现至少两次，则其endpos集合大小≥2。
在SAM构建过程中，我们可以计算出每个状态的endpos大小（通常记为cnt或size），方法如下：
- 每个终止状态（对应字符串的一个后缀）的cnt初始化为1。
- 按照link树（父节点为link(u)）自底向上（即按len从大到小）做拓扑排序，将子节点的cnt累加到父节点。
对于所有cnt[u] ≥ 2的状态，它能表示的最长子串长度为len[u]。
因此，答案就是所有满足cnt[u] ≥ 2的状态中，最大的len[u]。

算法步骤
假设已构建字符串s的SAM，状态数为state_num，数组len、link已知。

初始化cnt数组全0。
识别终止状态：从最后插入的状态last开始，沿link指针回溯到初始状态（状态0），沿途每个状态u的cnt[u] = 1。
按len对状态进行计数排序（桶排序），得到拓扑序order（len大的在前）。
遍历order，对每个状态u（非初始状态），执行cnt[link[u]] += cnt[u]。
遍历所有状态u，若cnt[u] ≥ 2，则用len[u]更新答案max_len。
最终max_len即为最长重复子串的长度。若要输出该子串，可在得到状态u后，沿转移反向走到初始状态，记录路径字符。

复杂度：构建SAM为O(n)，计数排序和cnt传递为O(n)，总时间O(n)，空间O(n·Σ)（Σ为字符集大小，可优化为Map）。

举例：字符串s = "ababa"。
构建SAM后，状态u（假设对应子串"aba"）的len[u]=3，cnt[u]=2（出现在位置0和2）。另一状态对应"ab"的len=2，cnt=3。最大len为3，即最长重复子串"aba"。

三、应用2：最小表示法

问题：给定字符串s，长度为n，将其所有循环同构的字符串（即s[i:] + s[:i]，0 ≤ i < n）中，找到字典序最小的一个。

常规算法：有O(n)的最小表示法（双指针），但这里我们用SAM展示其通用性。

思路分析

构造字符串T = s + s，则s的每个循环同构都是T的长度为n的子串。
问题转化为：在T的所有长度为n的子串中，找到字典序最小的一个。
在SAM中，字典序最小的子串可以通过在SAM上贪心行走得到：
- 从初始状态出发，每一步选择当前状态可转移的最小字符（ASCII最小）。
- 但这里要求子串长度恰好为n，且必须是T的子串。
技巧：对T构建SAM，然后在SAM上寻找字典序最小的长度为n的路径。
但构建T的SAM复杂度为O(2n)，可接受，但更优的方法是：构建s的SAM，然后将s再输入一遍（模拟扩展），同时记录路径。

算法步骤（基于s的SAM扩展）

构建字符串s的SAM。
设置当前状态u = 0（初始状态），当前匹配长度l = 0。
目标：在SAM上走n步，每一步选择可转移的最小字符，若没有转移，则沿link回退（相当于减少l），直到有转移为止。
具体步骤：
- 对于i从0到n-1（共需n步输出最小表示法的每个字符）：
  a. 如果当前状态u存在字符c（从'a'到'z'）的转移，则选择最小的c，转移到v = next[u][c]，l++，输出c，更新u = v。
  b. 如果不存在转移，则必须沿link回退：u = link[u]，l = len[u]（回退后l可能变小），然后重复尝试转移。
  c. 关键：在第一步中，我们可能已经因为之前的回退导致l > n？实际上，因为我们只走n步，且s的SAM只能识别长度≤n的子串，所以在处理T时，当l达到n，我们应模拟截断：即如果l == n，则我们执行一次u = link[u]和l = len[u]，相当于去掉当前子串的第一个字符，然后继续尝试扩展，以匹配T的后缀。
但实现时，更简单的方法：直接对T = s + s构建SAM，然后从初始状态开始，每次走最小字符，走n步，记录路径。这一步可在线性时间完成。

优化实现（不显式构建T的SAM）
我们可以利用s的SAM，并模拟读入第二个s的过程，同时用双指针思想：

已知最小表示法算法（非SAM）是O(n)，这里用SAM同样O(n)，但展示了SAM处理循环字符串的能力。
实际代码中，可以这样操作：
1. 构建s的SAM。
2. 状态u = 0，l = 0。
3. 对于i从0到n-1：
  - 若u没有当前最小字符转移，则u = link[u]，l = len[u]。
  - 设c为s[i % n]（即T的第i个字符），但我们要找最小，不是匹配。
    此方法稍复杂，因此实践中最小表示法多用标准双指针算法，但SAM方法在需要同时处理其他查询时有用。

举例：s = "bcba"，n=4。
T = "bcbabcb"。在SAM上走4步：
初始状态0，最小字符转移b->状态1，输出b；
状态1，最小字符c->状态2，输出c；
状态2，最小字符b->状态3，输出b；
状态3，最小字符a->状态4，输出a。
得到"bcba"，但需检查是否最小。实际上最小表示是"abcb"，因此上述贪心不直接适用于循环。正确做法应对T的每个起始位置检查，但SAM可快速比较字典序，需在SAM上维护起始位置。

更精确的SAM解法（对T建SAM）：

构建T的SAM。
在SAM上，从状态0开始，每次选最小字符走n步，得到路径即为最小表示。
原因：SAM包含了T的所有子串，且字典序最小路径对应最小子串。因为每一步都选最小字符，最终得到的是全局最小长度为n的子串。

复杂度：构建T的SAM为O(2n)，贪心走n步为O(n)，总O(n)。

总结
后缀自动机不仅是一个高效的后缀数据结构，还能通过其状态性质（endpos大小、len、link）解决多种字符串问题。

对于最长重复子串，关键是计算每个状态的endpos集合大小，筛选出大小≥2的状态中len最大者。
对于最小表示法，可通过构造双倍字符串的SAM，然后贪心走最小转移得到。

这两个应用体现了SAM在子串出现次数和字典序比较方面的强大能力，是深入掌握SAM的重要实践。

后缀自动机（Suffix Automaton）的应用：最长重复子串与最小表示法描述后缀自动机（SAM）是一种强大的数据结构，能在线性时间内构建出一个字符串的所有后缀的压缩表示。它不仅支持许多字符串查询（如子串出现次数、最长公共子串等），还能解决一些更复杂的问题。本次专题聚焦于两个经典应用：最长重复子串：在一个字符串中找到一个长度最大的子串，该子串在字符串中至少出现两次（允许重叠）。最小表示法：对于一个循环同构的字符串集合（如字符串的循环移位），找到字典序最小的那个表示。理解这些应用能加深对SAM本质（状态转移、 link 指针、 len 性质）的掌握，并体会其在字符串处理中的通用性。解题过程详解一、回顾后缀自动机（SAM）的核心性质在讲解应用前，我们先快速回顾SAM的关键点（假设已了解SAM基本构建，这里不重复状态转移函数 next 、后缀链接 link 、状态最大长度 len 等定义）： SAM的状态数不超过 2n-1 ，转移数不超过 3n-4 （n为字符串长度）。每个状态对应一个** endpos 等价类** ，即子串结束位置的集合。从初始状态出发，沿转移走出的每条路径对应原字符串的一个子串。状态 u 对应的所有子串长度连续，区间为 [len(link(u))+1, len(u)] 。沿着 link 指针向上走，相当于不断缩短当前子串（去掉首字符），形成后缀关系。二、应用1：最长重复子串问题：给定字符串 s ，求最长的子串，使得它在 s 中出现至少两次（出现位置可重叠）。思路分析重复子串意味着存在至少两个不同的起始位置 i 和 j ，使得 s[i:i+L] = s[j:j+L] 。在SAM中，一个子串对应从初始状态到达某个状态的某条路径。如果子串出现至少两次，则其 endpos 集合大小≥2。在SAM构建过程中，我们可以计算出每个状态的 endpos 大小（通常记为 cnt 或 size ），方法如下：每个终止状态（对应字符串的一个后缀）的 cnt 初始化为1。按照 link 树（父节点为 link(u) ）自底向上（即按 len 从大到小）做拓扑排序，将子节点的 cnt 累加到父节点。对于所有 cnt[u] ≥ 2 的状态，它能表示的最长子串长度为 len[u] 。因此，答案就是所有满足 cnt[u] ≥ 2 的状态中，最大的 len[u] 。算法步骤假设已构建字符串 s 的SAM，状态数为 state_num ，数组 len 、 link 已知。初始化 cnt 数组全0。识别终止状态：从最后插入的状态 last 开始，沿 link 指针回溯到初始状态（状态0），沿途每个状态 u 的 cnt[u] = 1 。按 len 对状态进行计数排序（桶排序），得到拓扑序 order （ len 大的在前）。遍历 order ，对每个状态 u （非初始状态），执行 cnt[link[u]] += cnt[u] 。遍历所有状态 u ，若 cnt[u] ≥ 2 ，则用 len[u] 更新答案 max_len 。最终 max_len 即为最长重复子串的长度。若要输出该子串，可在得到状态 u 后，沿转移反向走到初始状态，记录路径字符。复杂度：构建SAM为 O(n) ，计数排序和 cnt 传递为 O(n) ，总时间 O(n) ，空间 O(n·Σ) （Σ为字符集大小，可优化为Map）。举例：字符串 s = "ababa" 。构建SAM后，状态 u （假设对应子串"aba"）的 len[u]=3 ， cnt[u]=2 （出现在位置0和2）。另一状态对应"ab"的 len=2 ， cnt=3 。最大 len 为3，即最长重复子串"aba"。三、应用2：最小表示法问题：给定字符串 s ，长度为 n ，将其所有循环同构的字符串（即 s[i:] + s[:i] ， 0 ≤ i < n ）中，找到字典序最小的一个。常规算法：有 O(n) 的最小表示法（双指针），但这里我们用SAM展示其通用性。思路分析构造字符串 T = s + s ，则 s 的每个循环同构都是 T 的长度为 n 的子串。问题转化为：在 T 的所有长度为 n 的子串中，找到字典序最小的一个。在SAM中，字典序最小的子串可以通过在SAM上贪心行走得到：从初始状态出发，每一步选择当前状态可转移的最小字符（ASCII最小）。但这里要求子串长度恰好为 n ，且必须是 T 的子串。技巧：对 T 构建SAM，然后在SAM上寻找字典序最小的长度为 n 的路径。但构建 T 的SAM复杂度为 O(2n) ，可接受，但更优的方法是：构建 s 的SAM，然后将 s 再输入一遍（模拟扩展），同时记录路径。算法步骤（基于 s 的SAM扩展）构建字符串 s 的SAM。设置当前状态 u = 0 （初始状态），当前匹配长度 l = 0 。目标：在SAM上走 n 步，每一步选择可转移的最小字符，若没有转移，则沿 link 回退（相当于减少 l ），直到有转移为止。具体步骤：对于 i 从 0 到 n-1 （共需 n 步输出最小表示法的每个字符）： a. 如果当前状态 u 存在字符 c （从'a'到'z'）的转移，则选择最小的 c ，转移到 v = next[u][c] ， l++ ，输出 c ，更新 u = v 。 b. 如果不存在转移，则必须沿 link 回退： u = link[u] ， l = len[u] （回退后 l 可能变小），然后重复尝试转移。 c. 关键：在第一步中，我们可能已经因为之前的回退导致 l > n ？实际上，因为我们只走 n 步，且 s 的SAM只能识别长度≤n的子串，所以在处理 T 时，当 l 达到 n ，我们应模拟截断：即如果 l == n ，则我们执行一次 u = link[u] 和 l = len[u] ，相当于去掉当前子串的第一个字符，然后继续尝试扩展，以匹配 T 的后缀。但实现时，更简单的方法：直接对 T = s + s 构建SAM，然后从初始状态开始，每次走最小字符，走 n 步，记录路径。这一步可在线性时间完成。优化实现（不显式构建 T 的SAM）我们可以利用 s 的SAM，并模拟读入第二个 s 的过程，同时用双指针思想：已知最小表示法算法（非SAM）是 O(n) ，这里用SAM同样 O(n) ，但展示了SAM处理循环字符串的能力。实际代码中，可以这样操作：构建 s 的SAM。状态 u = 0 ， l = 0 。对于 i 从 0 到 n-1 ：若 u 没有当前最小字符转移，则 u = link[u] ， l = len[u] 。设 c 为 s[i % n] （即 T 的第 i 个字符），但我们要找最小，不是匹配。此方法稍复杂，因此实践中最小表示法多用标准双指针算法，但SAM方法在需要同时处理其他查询时有用。举例： s = "bcba" ， n=4 。 T = "bcbabcb" 。在SAM上走4步：初始状态0，最小字符转移 b ->状态1，输出 b ；状态1，最小字符 c ->状态2，输出 c ；状态2，最小字符 b ->状态3，输出 b ；状态3，最小字符 a ->状态4，输出 a 。得到 "bcba" ，但需检查是否最小。实际上最小表示是 "abcb" ，因此上述贪心不直接适用于循环。正确做法应对 T 的每个起始位置检查，但SAM可快速比较字典序，需在SAM上维护起始位置。更精确的SAM解法（对 T 建SAM）：构建 T 的SAM。在SAM上，从状态0开始，每次选最小字符走 n 步，得到路径即为最小表示。原因：SAM包含了 T 的所有子串，且字典序最小路径对应最小子串。因为每一步都选最小字符，最终得到的是全局最小长度为 n 的子串。复杂度：构建 T 的SAM为 O(2n) ，贪心走 n 步为 O(n) ，总 O(n) 。总结后缀自动机不仅是一个高效的后缀数据结构，还能通过其状态性质（ endpos 大小、 len 、 link ）解决多种字符串问题。对于最长重复子串，关键是计算每个状态的 endpos 集合大小，筛选出大小≥2的状态中 len 最大者。对于最小表示法，可通过构造双倍字符串的SAM，然后贪心走最小转移得到。这两个应用体现了SAM在子串出现次数和字典序比较方面的强大能力，是深入掌握SAM的重要实践。