SAM算法Python实现详解：从原理到高效字符串处理241

在计算机科学领域，字符串处理是无处不在的基础任务。从简单的文本搜索到复杂的生物信息学分析，高效的字符串算法是解决问题的关键。后缀自动机（Suffix Automaton, SAM）作为一种强大而优雅的字符串数据结构，以其线性的时间复杂度在构建和查询方面表现出色，能够解决许多传统算法难以高效处理的问题。本文将深入探讨SAM的原理、核心概念、Python实现细节，并展示其在实际应用中的强大能力。

1. 什么是后缀自动机（Suffix Automaton, SAM）？

后缀自动机（SAM）是一种接受给定字符串所有子串的最小确定性有限自动机（Minimal Deterministic Finite Automaton, MDFA）。简单来说，它可以被视为对一个字符串所有子串的紧凑表示。虽然后缀树（Suffix Tree）和后缀数组（Suffix Array）也能实现类似的功能，但SAM在空间复杂度和构建复杂度上往往更优，并且在线性时间内完成构建，这使得它在处理动态字符串或大规模数据时具有独特的优势。

SAM的每个状态都对应着原字符串的一些子串，这些子串在原字符串中具有相同的“结束位置集合”（endpos set）。`endpos(s)` 被定义为字符串 `s` 在原字符串中所有出现结束位置的集合。如果两个子串 `s1` 和 `s2` 的 `endpos` 集合相同，则它们将映射到SAM中的同一个状态。这种性质是SAM精巧设计的核心。

2. SAM的核心概念与结构

理解SAM需要掌握其状态（State）和状态之间的关系。SAM的每个状态通常包含以下关键信息：

`len` (length): 该状态所代表的最长子串的长度。一个状态代表的所有子串都以 `len[link_state] + 1` 到 `len[current_state]` 的长度范围。其中 `link_state` 是其后缀链接指向的状态。

`link` (suffix link): 后缀链接指向的状态。对于一个状态 `u`，其 `link[u]` 指向的状态 `v` 代表着 `u` 所代表的所有子串中最长的那个串的最长后缀，且该后缀在原字符串中出现的 `endpos` 集合与 `u` 的 `endpos` 集合不同（即是 `u` 的 `endpos` 集合的超集）。后缀链接构成了SAM中的一棵树（或森林），称为后缀链接树（Suffix Link Tree）。

`next` (transitions): 一个字典或哈希表，表示从当前状态通过某个字符能到达的下一个状态。例如，`next[char]` 表示通过字符 `char` 从当前状态转移到的下一个状态。

SAM的构建过程是增量式的，即每次向字符串末尾添加一个字符。通过巧妙地更新 `len`、`link` 和 `next`，我们可以保持SAM的性质。

3. SAM的构建算法（Python实现）

SAM的构建是一个在线算法，这意味着我们可以逐个字符地构建它。假设我们已经构建了字符串 `S` 的SAM，现在要添加一个字符 `c` 来构建 `S+c` 的SAM。这个过程由一个 `extend` 操作完成，时间复杂度为 O(1) 均摊。

我们用一个 `states` 列表（或字典）来存储所有状态，每个状态是一个字典或对象，包含 `len`, `link`, `next`。`` 变量始终指向当前处理的字符串的最长后缀对应的状态。

构建流程（`extend` 函数的核心逻辑）：

创建一个新状态 `new_state`，其 `len` 值为 ` + 1`。初始时 `` 为 `-1`（表示未确定，或指向根节点），`` 为空。

从 `` 开始，沿着后缀链接 `p = ` 向上遍历。对于每个 `p`：

如果 `p` 还没有到字符 `c` 的转移，则将 `p` 到 `new_state` 的转移添加进去：`[c] = new_state`。

如果 `p` 已经有到字符 `c` 的转移 `q = [c]`，则跳出循环。这意味着我们找到了一个公共的后缀路径。

处理 `new_state` 的后缀链接：

情况1：如果循环结束后 `p` 变为 `None`（即遍历到了根节点），说明 `new_state` 没有任何前缀与现有状态有公共后缀，因此 ` = ` (根节点)。

情况2：如果循环结束后 `p` 没有变为 `None`，说明 `p` 有一个到 `q = [c]` 的转移。

子情况2a：如果 ` == + 1`，说明 `q` 已经是一个“规范”状态，可以直接将 ` = q`。

子情况2b：如果 ` > + 1`，这表示 `q` 所代表的字符串比我们期望的要长。我们需要“克隆” `q`。

创建一个新的克隆状态 `clone_state`，复制 `q` 的 `len`（但设置为 ` + 1`），`link` 和 `next`。

更新 `q` 的 `link` 为 `clone_state`。

更新 `new_state` 的 `link` 为 `clone_state`。

从 `p` 开始沿着后缀链接再次向上遍历，对于所有通过 `c` 指向 `q` 的状态 `cur`，将其指向 `clone_state`：`[c] = clone_state`。

最后，更新 ` = new_state`。

4. SAM的Python代码示例

以下是SAM的Python实现，包括构建和计算不同子串数量的方法。class SAMNode:
"""
后缀自动机的一个状态节点
len: 该状态代表的最长字符串的长度
link: 后缀链接，指向最长后缀对应的状态
next: 转移字典，字符 -> 目标状态
is_clone: 标记是否是克隆节点（在计数不同子串时有用，因为克隆节点不对应实际的endpos集合）
"""
__slots__ = ['length', 'link', 'next_transitions', 'is_clone', 'is_terminal']
def __init__(self, length=0, link=-1, is_clone=False):
= length
= link
self.next_transitions = {}
self.is_clone = is_clone
self.is_terminal = False # 用于标记是否是原字符串的某个前缀对应的状态
class SuffixAutomaton:
"""
后缀自动机实现
"""
def __init__(self):
= [SAMNode()] # 状态0是根节点
= 0 # last 指向当前处理的字符串的最长后缀对应的状态
= 1 # 当前状态数量
def add_char(self, char):
"""
向自动机中添加一个字符
"""
current_node_idx =
(SAMNode(length=[].length + 1))
+= 1
p =
# 沿着后缀链接向上遍历，为所有不能通过char到达新状态的p添加转移
while p != -1 and char not in [p].next_transitions:
[p].next_transitions[char] = current_node_idx
p = [p].link
# 处理后缀链接
if p == -1:
# 情况1: p遍历到根节点，新状态的后缀链接指向根节点
[current_node_idx].link = 0
else:
# 情况2: p找到了一个转移q
q = [p].next_transitions[char]
if [q].length == [p].length + 1:
# 子情况2a: q是p的合法转移，新状态的后缀链接指向q
[current_node_idx].link = q
else:
# 子情况2b: q的长度不合法，需要克隆q
clone_node_idx =
(SAMNode(
length=[p].length + 1,
link=[q].link,
is_clone=True
))
[clone_node_idx].next_transitions = [q].()
+= 1
# 更新q和新状态的后缀链接指向克隆状态
[q].link = clone_node_idx
[current_node_idx].link = clone_node_idx
# 再次向上遍历，将所有指向q的p的转移改为指向克隆状态
while p != -1 and [p].(char) == q:
[p].next_transitions[char] = clone_node_idx
p = [p].link

= current_node_idx
# 标记所有通过能到达的状态都是原字符串前缀的结尾
# (这步在实际中通常在最后统一标记，或根据应用需求决定是否需要)
# current_terminal =
# while current_terminal != -1:
# [current_terminal].is_terminal = True
# current_terminal = [current_terminal].link

def build(self, s):
"""
构建字符串s的后缀自动机
"""
for char_code in s: # 使用ord(char)来处理字符，或者直接用char如果只处理ASCII
self.add_char(char_code)

# 标记所有原始状态（非克隆）为终端状态
# 实际应用中，标记终端状态是为了计算原字符串的某些性质，
# 例如子串出现次数等。对于不同子串计数，这一步不是必须的。
curr =
while curr != -1:
[curr].is_terminal = True
curr = [curr].link

def count_distinct_substrings(self):
"""
计算字符串中不同子串的数量
"""
count = 0
for i in range(1, ): # 忽略根节点
# 每个状态代表的子串数量 = 该状态的最长子串长度 - 后缀链接指向的状态的最长子串长度
# 这些子串共享相同的endpos集合
count += [i].length - [[i].link].length
return count
def has_substring(self, pattern):
"""
检查pattern是否为原字符串的子串
"""
current_state = 0 # 从根节点开始
for char_code in pattern:
if char_code in [current_state].next_transitions:
current_state = [current_state].next_transitions[char_code]
else:
return False
return True
# 示例使用
if __name__ == "__main__":
text = "banana"
sam = SuffixAutomaton()
(text)
print(f"字符串 '{text}' 的不同子串数量: {sam.count_distinct_substrings()}") # 预期输出: 15
print(f"是否存在子串 'ban': {sam.has_substring('ban')}") # 预期输出: True
print(f"是否存在子串 'nan': {sam.has_substring('nan')}") # 预期输出: True
print(f"是否存在子串 'anna': {sam.has_substring('anna')}") # 预期输出: True
print(f"是否存在子串 'apple': {sam.has_substring('apple')}") # 预期输出: False
text2 = "ababa"
sam2 = SuffixAutomaton()
(text2)
print(f"字符串 '{text2}' 的不同子串数量: {sam2.count_distinct_substrings()}") # 预期输出: 10
# 打印部分状态信息（调试用）
# for i, node in enumerate():
# print(f"State {i}: len={}, link={}, next={node.next_transitions}")

5. SAM的应用场景

SAM不仅仅是一个理论概念，它在实际问题中有着广泛而高效的应用：

计算不同子串的数量： 这是SAM最直接的应用之一。每个状态 `u` 代表 `len[u] - len[link[u]]` 个不同子串。将所有状态的这个值相加即可得到总的不同子串数量。

子串查找： 通过遍历SAM，可以 O(|pattern|) 的时间复杂度检查一个模式串是否存在于原字符串中。

最长公共子串： 给定两个字符串 S1 和 S2，可以先构建 S1 的SAM。然后用 S2 在 S1 的SAM上进行匹配，维护当前匹配的长度和状态。匹配过程中经过的路径就对应公共子串，记录最长匹配长度即可。

子串的出现次数： 在SAM构建完成后，通过在后缀链接树上进行DFS或拓扑排序，可以计算每个状态对应的字符串在原串中出现的次数。克隆状态需要特殊处理。

字典序第K小/大子串： 利用SAM的结构，可以在每个状态上预计算从该状态出发能到达的子串数量，然后进行路径选择。

最小循环位移： 将字符串 `S` 复制一份得到 `S+S`，然后构建这个新串的SAM。在SAM上找到一个长度为 `|S|` 的最小字典序路径，即可得到最小循环位移。

6. SAM的优势与局限性

优势：

线性时间复杂度： SAM的构建时间复杂度为 O(N)，N 为字符串长度，这是非常高效的。

空间效率： 相较于后缀树，SAM的状态数和转移数都更少（最多 2N-1 个状态，3N-4 条转移），因此空间占用更小。

功能强大： 能够解决几乎所有后缀树能解决的问题，并且在某些场景下更为简洁。

在线构建： 能够逐个字符地添加，适用于流式数据处理。

局限性：

概念复杂： 相对于后缀数组，SAM的内部机制（尤其是后缀链接和克隆操作）理解起来更抽象。

实现细节较多： `extend` 函数的逻辑相对精巧，容易出错。

7. 结论

后缀自动机（SAM）是字符串算法领域的一个瑰宝。它以线性的时间复杂度和紧凑的空间表示，为众多复杂的字符串问题提供了优雅高效的解决方案。通过本文的原理阐述、Python代码示例及其详尽的应用场景分析，相信您对SAM有了更深入的理解。掌握SAM不仅能提升您在算法竞赛中的竞争力，也能在实际开发中为高效字符串处理提供强大的工具。虽然其实现细节可能需要一些时间和练习才能完全掌握，但其带来的回报是巨大的。

鼓励读者动手实践代码，通过调试和修改来加深对SAM工作原理的理解。只有通过实践，才能真正领悟这种数据结构的精妙之处。

2026-03-31

---

上一篇：Python函数参数深度解析：定义、输入与高级用法

下一篇：调用 Python 代码：深度解析多场景集成与高效实践指南