高效处理字符串的利器（Python后缀自动机从零实现详解）

什么是后缀自动机？

后缀自动机是一个有向无环图（DAG），它可以表示一个字符串的所有后缀，并且每个状态代表一组具有相同“右上下文”的子串。简单来说，它能以最小状态数压缩地存储所有子串信息。

它的核心优势包括：

• 构建时间复杂度为 O(n)
• 空间复杂度为 O(n)
• 支持快速子串匹配和统计

Python后缀自动机实现步骤

我们将逐步构建一个后缀自动机类。整个实现基于经典的 SAM 构建算法，使用“克隆”技术来维护状态转移的正确性。

1. 定义状态节点

每个状态包含以下属性：

• length：该状态能表示的最长子串长度
• link：后缀链接（指向更短后缀的状态）
• next：字符到下一个状态的映射字典

2. 核心构建逻辑

我们逐个添加字符，并动态维护自动机结构。关键在于处理“分裂”情况——当某个状态的转移会导致不一致时，我们需要克隆该状态。

3. 完整代码实现

class SuffixAutomaton:    def __init__(self):        # 初始化状态列表，每个状态是一个字典        self.states = [{'length': 0, 'link': -1, 'next': {}}]        self.last = 0  # 当前最后一个状态的索引        self.size = 1  # 状态总数    def extend(self, c):        """向自动机中添加一个字符 c"""        cur = self.size        self.states.append({            'length': self.states[self.last]['length'] + 1,            'link': -1,            'next': {}        })        self.size += 1        p = self.last        # 沿着后缀链接向上，设置转移        while p != -1 and c not in self.states[p]['next']:            self.states[p]['next'][c] = cur            p = self.states[p]['link']        if p == -1:            self.states[cur]['link'] = 0        else:            q = self.states[p]['next'][c]            if self.states[p]['length'] + 1 == self.states[q]['length']:                self.states[cur]['link'] = q            else:                # 需要克隆状态 q                clone = self.size                self.states.append({                    'length': self.states[p]['length'] + 1,                    'link': self.states[q]['link'],                    'next': self.states[q]['next'].copy()                })                self.size += 1                # 更新 q 和 cur 的后缀链接                while p != -1 and self.states[p]['next'].get(c) == q:                    self.states[p]['next'][c] = clone                    p = self.states[p]['link']                                self.states[q]['link'] = clone                self.states[cur]['link'] = clone        self.last = cur    def build(self, s):        """从字符串 s 构建后缀自动机"""        for char in s:            self.extend(char)    def count_distinct_substrings(self):        """计算不同子串的数量"""        total = 0        for i in range(1, self.size):            total += self.states[i]['length'] - self.states[self.states[i]['link']]['length']        return total

如何使用这个后缀自动机？

下面是一个简单的使用示例：

# 创建自动机并构建sa = SuffixAutomaton()sa.build("ababa")# 计算不同子串数量print(sa.count_distinct_substrings())  # 输出: 9

对于字符串 "ababa"，其所有不同子串为：a, b, ab, ba, aba, bab, abab, baba, ababa，共9个，与结果一致。

为什么学习后缀自动机？

掌握字符串算法Python实现是进阶编程的重要一步。后缀自动机作为高级数据结构，在竞赛、文本挖掘、生物信息学等领域有广泛应用。通过本教程，你不仅学会了后缀自动机实现，还深入理解了自动机数据结构的设计思想。

总结

本文详细讲解了如何用Python后缀自动机从零开始构建一个功能完整的后缀自动机。通过清晰的代码结构和注释，即使是初学者也能理解其工作原理。希望你能将这一强大工具应用到实际项目中！

提示：你可以在此基础上扩展功能，例如支持子串出现次数统计、最长回文子串查找等。