深入理解后缀自动机（Suffix Automaton）

什么是后缀自动机？

后缀自动机是一个有向图，它能表示一个字符串的所有子串。更准确地说，它是该字符串所有后缀的最小确定有限状态自动机（DFA）。它的核心优势在于：

• 空间复杂度为 O(n)，其中 n 是字符串长度；
• 构建时间复杂度为 O(n)；
• 可以快速判断任意字符串是否为原字符串的子串。

后缀自动机的基本结构

每个状态（节点）代表一组 endpos 等价类（即子串结束位置集合相同的子串）。每个状态包含以下信息：

• len：该状态中最长子串的长度；
• link：后缀链接，指向另一个状态；
• next：字符转移字典，记录从当前状态通过某个字符能到达的状态。

Python 实现后缀自动机

下面我们用 Python后缀自动机 的方式一步步实现这个算法。代码清晰易懂，适合初学者理解。

class SAMNode:    def __init__(self):        self.len = 0          # 当前状态最长子串长度        self.link = -1        # 后缀链接        self.next = {}        # 字符转移字典class SuffixAutomaton:    def __init__(self):        self.nodes = [SAMNode()]  # 初始状态        self.last = 0             # 最后一个状态的索引    def extend(self, c):        """向自动机中添加一个字符 c"""        cur = len(self.nodes)        self.nodes.append(SAMNode())        self.nodes[cur].len = self.nodes[self.last].len + 1        p = self.last        # 沿着后缀链接向上，设置转移        while p != -1 and c not in self.nodes[p].next:            self.nodes[p].next[c] = cur            p = self.nodes[p].link        if p == -1:            self.nodes[cur].link = 0        else:            q = self.nodes[p].next[c]            if self.nodes[p].len + 1 == self.nodes[q].len:                self.nodes[cur].link = q            else:                # 克隆节点 q                clone = len(self.nodes)                self.nodes.append(SAMNode())                self.nodes[clone].len = self.nodes[p].len + 1                self.nodes[clone].next = self.nodes[q].next.copy()                self.nodes[clone].link = self.nodes[q].link                # 更新 q 和 cur 的 link                self.nodes[q].link = clone                self.nodes[cur].link = clone                # 更新之前指向 q 的转移                while p != -1 and self.nodes[p].next.get(c) == q:                    self.nodes[p].next[c] = clone                    p = self.nodes[p].link        self.last = cur    def build(self, s):        """从字符串 s 构建后缀自动机"""        for char in s:            self.extend(char)    def contains(self, substr):        """检查 substr 是否为原字符串的子串"""        node = 0        for c in substr:            if c not in self.nodes[node].next:                return False            node = self.nodes[node].next[c]        return True

使用示例

下面是如何使用我们刚实现的后缀自动机：

# 创建自动机并构建sa = SuffixAutomaton()sa.build("abcbc")# 查询子串print(sa.contains("bc"))   # Trueprint(sa.contains("ac"))   # Falseprint(sa.contains("cbc"))  # True

应用场景

后缀自动机在实际开发中有广泛用途，包括但不限于：

• 文本编辑器中的快速搜索功能；
• 生物信息学中的 DNA 序列比对；
• 压缩算法中的重复模式检测；
• 解决 LeetCode 等平台上的高级字符串题目。

总结

通过本教程，我们了解了后缀自动机算法的基本原理，并用 Python 实现了一个完整的版本。虽然初看可能有些复杂，但只要理解了状态、转移和后缀链接的作用，就能掌握这一强大工具。希望这篇面向小白的教程能帮助你开启高效Python字符串匹配的大门！

记住，实践是最好的老师。尝试修改代码、测试不同字符串，你会对后缀自动机有更深的理解。