数据结构：后缀自动机
最新推荐文章于 2025-12-16 16:07:35 发布
原创最新推荐文章于 2025-12-16 16:07:35 发布·791 阅读
14·
·
9
· 9 14·CC 4.0 BY-SA版权
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。
文章标签：
后缀自动机
资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf
一、后缀自动机的定义
后缀自动机（Suffix Automaton，简称 SAM）是一种压缩存储字符串所有子串的高效有限状态自动机，能够以O(n) 的空间和时间复杂度表示字符串的所有后缀（及所有子串），是处理字符串子串相关问题的核心数据结构。
SAM 的核心特征：
- 压缩性：通过合并等价状态，仅用
O(n)个状态和转移边表示长度为n的字符串的所有子串（总子串数为n(n+1)/2，直接存储不可行）； - 高效性：构建时间/空间复杂度均为
O(n)，支持子串查询、不同子串计数、最长重复子串等问题的线性/对数时间求解。
二、后缀自动机的核心概念
1. 状态（State）
SAM 的每个状态代表一组等价的子串（称为“等价类”），满足：
- 这些子串在字符串中出现的结束位置集合（endpos） 完全相同；
- 每个状态关联核心属性：
len：该状态表示的子串的最大长度；link：后缀链接，指向另一个状态，表示当前状态的子串去掉首字符后的等价状态（构成一棵后缀树）；trans：转移字典，键为字符，值为转移后的状态，表示在当前子串末尾添加该字符后的等价状态。
2. 结束位置集合（endpos）
对于字符串S 的子串t，endpos(t) 是t 在S 中所有结束位置的集合。例如S = "ababa"，子串"aba" 的endpos = {2,4}。
- 等价状态：
endpos相同的子串属于同一状态； - 状态的
len：该状态所有子串的最大长度，最小长度为link状态的len + 1。
3. 后缀链接（link）
后缀链接是 SAM 的核心结构，满足：
- 若状态
u的后缀链接指向v，则endpos(v) ⊇ endpos(u)； - 所有状态的后缀链接构成一棵以初始状态（空串状态）为根的树。
4. 初始状态与终止状态
- 初始状态（起始状态）：表示空串，
len = 0，link = -1（无父节点）； - 终止状态：所有能通过后缀链接最终到达初始状态，且对应子串为原字符串后缀的状态（可通过构建时标记）。
三、后缀自动机的构建原理
SAM 的构建采用增量法：逐个添加字符串的字符，动态扩展状态和转移，核心步骤为“新建状态 → 扩展转移 → 分裂状态（若需） → 更新后缀链接”。
核心步骤（增量法）
- 新建状态
cur：添加字符c时，新建状态cur，其len = last.len + 1（last为上一个字符对应的状态）。 - 扩展转移：从
last出发，沿后缀链接向上遍历，为所有无c转移的状态添加指向cur的转移，直到初始状态或找到有c转移的状态p。 - 处理转移冲突：若
p不存在（遍历到初始状态），则cur.link = 初始状态；否则找到p通过c转移的状态q：- 若
q.len = p.len + 1：直接令cur.link = q； - 若
q.len > p.len + 1：分裂q为clone状态（复制q的trans和link，clone.len = p.len + 1），更新q和cur的link为clone，并修正p及其后缀链路上状态的c转移（指向clone而非q）。
- 若
- 更新
last：令last = cur，继续添加下一个字符。
四、后缀自动机的实现示例
classState:def__init__(self): self.len=0# 状态表示的子串的最大长度 self.link=-1# 后缀链接 self.trans=dict()# 转移字典: {字符: 状态索引}classSuffixAutomaton:def__init__(self): self.size=1# 状态总数，初始状态为0 self.last=0# 最后一个状态的索引 self.states=[State()]# 状态列表defsa_extend(self, c):"""增量添加字符c，扩展SAM""" cur= self.size self.size+=1 self.states.append(State()) self.states[cur].len= self.states[self.last].len+1 p= self.last# 沿后缀链接向上，添加转移while p!=-1and cnotin self.states[p].trans: self.states[p].trans[c]= cur p= self.states[p].linkif p==-1:# 遍历到初始状态，cur的后缀链接指向初始状态 self.states[cur].link=0else: q= self.states[p].trans[c]if self.states[p].len+1== self.states[q].len:# q是p添加c后的直接状态，cur的后缀链接指向q self.states[cur].link= qelse:# 分裂q为clone状态 clone= self.size self.size+=1 self.states.append(State()) self.states[clone].len= self.states[p].len+1 self.states[clone].trans= self.states[q].trans.copy() self.states[clone].link= self.states[q].link# 更新p及其后缀链路上指向q的转移为clonewhile p!=-1and self.states[p].trans.get(c,-1)== q: self.states[p].trans[c]= clone p= self.states[p].link# 更新q和cur的后缀链接 self.states[q].link= clone self.states[cur].link= clone self.last= curdefbuild(self, s):"""构建字符串s的SAM"""for cin s: self.sa_extend(c)defcount_distinct_substrings(self):"""统计字符串的不同子串数量""" res=0for iinrange(1, self.size):# 每个状态贡献的子串数 = len[i] - len[link[i]] res+= self.states[i].len- self.states[self.states[i].link].lenreturn resdefis_substring(self, t):"""判断t是否是原字符串的子串""" p=0# 从初始状态开始for cin t:if cnotin self.states[p].trans:returnFalse p= self.states[p].trans[c]returnTrue使用示例
# 构建SAMs="abracadabra"sam= SuffixAutomaton()sam.build(s)# 统计不同子串数量print("不同子串数量:", sam.count_distinct_substrings())# 输出 53# 子串查询print("是否包含子串 'abra':", sam.is_substring("abra"))# 输出 Trueprint("是否包含子串 'xyz':", sam.is_substring("xyz"))# 输出 False# 最长重复子串（需额外遍历状态计算）deflongest_repeated_substring(sam): max_len=0for iinrange(1, sam.size): link_len= sam.states[sam.states[i].link].len# 重复子串需满足：该状态的子串出现至少两次（endpos大小≥2）# 简化版：通过len - link_len判断可能的最大长度（精确判断需统计endpos）if sam.states[i].len> max_lenand link_len>0: max_len= sam.states[i].lenreturn max_lenprint("最长重复子串长度:", longest_repeated_substring(sam))# 输出 4（如"abra"）五、后缀自动机的核心操作与时间复杂度
| 操作 | 描述 | 时间复杂度 |
|---|---|---|
| 构建 SAM | 增量添加字符，动态扩展状态 | O(n) |
| 子串存在性查询 | 沿转移边遍历 | `O( |
| 不同子串计数 | 遍历所有状态计算贡献 | O(n) |
| 最长重复子串 | 遍历状态找最大len | O(n) |
| 最长公共子串（两字符串） | 构建一个字符串的SAM，遍历另一个字符串 | O(n+m) |
六、后缀自动机的典型应用
- 不同子串计数：核心公式为
∑(len[i] - len[link[i]])（所有状态的贡献和）； - 子串存在性查询：线性时间判断一个字符串是否是原字符串的子串；
- 最长重复子串：找到最大的
len[i]，满足该状态的子串出现至少两次； - 最长公共子串：对字符串
S构建 SAM，用字符串T遍历 SAM，记录遍历过程中的最大长度； - 子串出现次数统计：通过拓扑排序统计每个状态的
endpos大小（子串出现次数）； - 多字符串公共子串：构建多个字符串的 SAM，合并状态后求解。
七、后缀自动机与其他字符串结构的对比
| 数据结构 | 构建复杂度 | 空间复杂度 | 核心优势 | 适用场景 |
|---|---|---|---|---|
| 后缀自动机 | 较复杂 | O(n) | 空间最优，支持动态添加 | 海量字符串的子串问题 |
| 后缀数组 | 中等 | O(n log n) | 直观，支持LCP问题 | 重复子串、公共子串 |
| 字典树（Trie） | 简单 | O(n) | 前缀匹配高效 | 前缀查询、词频统计 |
SAM 的核心优势是空间和时间效率极致，尤其适合处理超长字符串（如百万级字符）的子串问题，缺点是理解和实现难度较高；而后缀数组更直观，适合入门级字符串子串问题。
扫一扫
参与评论您还未登录，请先登录后发表或查看评论
09-01
2596
2596
到【灌水乐园】发言
