数据结构：后缀自动机

后缀自动机

资料：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 的构建采用增量法：逐个添加字符串的字符，动态扩展状态和转移，核心步骤为“新建状态 → 扩展转移 → 分裂状态（若需） → 更新后缀链接”。

核心步骤（增量法）

1. 新建状态cur：添加字符c时，新建状态cur，其len = last.len + 1（last为上一个字符对应的状态）。
2. 扩展转移：从last出发，沿后缀链接向上遍历，为所有无c转移的状态添加指向cur的转移，直到初始状态或找到有c转移的状态p。
3. 处理转移冲突：若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）。
4. 更新last：令last = cur，继续添加下一个字符。

四、后缀自动机的实现示例

classState:def__init__(self):self.len=0# 状态表示的子串的最大长度self.link=-1# 后缀链接self.trans=dict()# 转移字典: {字符: 状态索引}classSuffixAutomaton:def__init__(self):self.size=1# 状态总数，初始状态为0self.last=0# 最后一个状态的索引self.states=[State()]# 状态列表defsa_extend(self,c):"""增量添加字符c，扩展SAM"""cur=self.size self.size+=1self.states.append(State())self.states[cur].len=self.states[self.last].len+1p=self.last# 沿后缀链接向上，添加转移whilep!=-1andcnotinself.states[p].trans:self.states[p].trans[c]=cur p=self.states[p].linkifp==-1:# 遍历到初始状态，cur的后缀链接指向初始状态self.states[cur].link=0else:q=self.states[p].trans[c]ifself.states[p].len+1==self.states[q].len:# q是p添加c后的直接状态，cur的后缀链接指向qself.states[cur].link=qelse:# 分裂q为clone状态clone=self.size self.size+=1self.states.append(State())self.states[clone].len=self.states[p].len+1self.states[clone].trans=self.states[q].trans.copy()self.states[clone].link=self.states[q].link# 更新p及其后缀链路上指向q的转移为clonewhilep!=-1andself.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"""forcins:self.sa_extend(c)defcount_distinct_substrings(self):"""统计字符串的不同子串数量"""res=0foriinrange(1,self.size):# 每个状态贡献的子串数 = len[i] - len[link[i]]res+=self.states[i].len-self.states[self.states[i].link].lenreturnresdefis_substring(self,t):"""判断t是否是原字符串的子串"""p=0# 从初始状态开始forcint:ifcnotinself.states[p].trans:returnFalsep=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=0foriinrange(1,sam.size):link_len=sam.states[sam.states[i].link].len# 重复子串需满足：该状态的子串出现至少两次（endpos大小≥2）# 简化版：通过len - link_len判断可能的最大长度（精确判断需统计endpos）ifsam.states[i].len>max_lenandlink_len>0:max_len=sam.states[i].lenreturnmax_lenprint("最长重复子串长度:",longest_repeated_substring(sam))# 输出 4（如"abra"）

五、后缀自动机的核心操作与时间复杂度

六、后缀自动机的典型应用

1. 不同子串计数：核心公式为∑(len[i] - len[link[i]])（所有状态的贡献和）；
2. 子串存在性查询：线性时间判断一个字符串是否是原字符串的子串；
3. 最长重复子串：找到最大的len[i]，满足该状态的子串出现至少两次；
4. 最长公共子串：对字符串S构建 SAM，用字符串T遍历 SAM，记录遍历过程中的最大长度；
5. 子串出现次数统计：通过拓扑排序统计每个状态的endpos大小（子串出现次数）；
6. 多字符串公共子串：构建多个字符串的 SAM，合并状态后求解。

七、后缀自动机与其他字符串结构的对比

SAM 的核心优势是空间和时间效率极致，尤其适合处理超长字符串（如百万级字符）的子串问题，缺点是理解和实现难度较高；而后缀数组更直观，适合入门级字符串子串问题。