后缀自动机解析：本质不同子串与最长重复片段统计

引言2026 南昌市中小学生信息学奥林匹克竞赛报名正在火热进行9 月 29 日—10 月 16 日10 月 25 日开赛提高组考纲把特殊树哈希表搜索与图论都列了进去而字符串处理作为信奥进阶的硬骨头几乎贯穿从普及组到省选的每一场实战。提到字符串很多同学的第一反应是 KMP 或者哈希但当你要回答一个串里本质不同的子串有多少个最长的重复片段有多长某个片段出现过几次这类问题时暴力枚举会瞬间退化成指数级。本期我们请出字符串算法的终极大杀器——后缀自动机Suffix Automaton简称 SAM用一份呼号库的小项目带你一次性吃透它的构造与三大高频应用。一、题目目标校园广播台呼号库广播台每天会播报一长串由字母组成的呼号串S例如ababa。运营同学想做一个检索系统需要支持三个功能本质不同子串统计S中一共有多少个互不相同的子串空串不算。最长重复片段找出出现次数 ≥ 2 的最长子串的长度即被重复播报过的最长呼号片段。片段出现次数查询给定一个查询串t返回它在S中作为子串出现的次数每处起止位置都算一次。直接枚举所有子串再丢进set去重时间复杂度是O(|S|²)还要乘上插入set的代价一旦|S|到10⁵就彻底爆掉。后缀自动机能在O(|S|)的时间和空间内建好结构把上面三个问题都压到近乎线性。二、核心考点拆解后缀自动机之所以强是因为它用一个最简状态自动机存下了原串的所有子串且每个状态恰好对应一族结尾位置集合endpos相同的子串。吃透下面 7 个点SAM 就不再是黑盒endpos 等价类所有在原串中结束位置集合相同的子串被压缩进同一个状态。SAM 的状态数 ≤2|S|−1。len数组每个状态v代表的一族子串里最长的那条长度就是len[v]最短的是len[link[v]] 1。后缀链接linkparent 树link[v]指向v 代表子串的最长真后缀、且与 v 的 endpos 不同的那个状态。所有link连起来是一棵以根空串为祖先的树。增量构造extend(c)从空串开始逐字符往右接每次只新建/调整常数个状态保证O(|S|)。转移next状态v经过字符c到达的状态表示在 v 代表子串后追加 c。克隆节点clone当某个状态q被半路截胡时必须把q拆出一个克隆点保证自动机仍然最小——这是 SAM 最容易写错的地方。cnt累加endpos 大小每个实点真正由某次extend新建的整串前缀初始cnt 1按len从大到小沿link向上汇总就得到每个状态子串的出现次数。build_cnt写成幂等先重置再累加多次调用也不会把计数翻倍。三、解法与逐步实现3.1 本质不同子串个数每个状态v贡献的新子串数 len[v] − len[link[v]]从最短那条到最长那条刚好这段长度区间里的子串都只在 v 里首次出现。把所有v ≠ 根加起来即可复杂度O(|S|)。3.2 最长重复片段先跑一遍cnt累加然后扫描所有状态只要某个状态的cnt ≥ 2说明它代表的子串至少出现了两次就用它的len去更新最大值。3.3 片段出现次数查询把查询串t在自动机上顺着next一位位走走不动某字符无转移说明t不是子串返回 0否则停在哪状态v返回cnt[v]即可同一状态的所有子串出现次数相同。3.4 Python 完整实现class SAM: 后缀自动机支持本质不同子串计数、最长重复子串、子串出现次数查询。 def __init__(self, s: str): self.len [0] # 每个状态的 len self.link [-1] # 后缀链接根节点为 -1 self.next [dict()] # 转移字符 - 状态编号 self.cnt [0] # endpos 集合大小出现次数 self.real [False] # 实点真实前缀状态才初始 cnt1克隆点为 False self.last 0 for ch in s: self._extend(ch) def _extend(self, c: str): cur len(self.len) self.len.append(0) self.link.append(0) self.next.append(dict()) self.cnt.append(0) self.real.append(True) # 新整串前缀 实点 self.len[cur] self.len[self.last] 1 # 新状态长度 上一整串长度 1 p self.last while p ! -1 and c not in self.next[p]: self.next[p][c] cur p self.link[p] if p -1: self.link[cur] 0 else: q self.next[p][c] if self.len[p] 1 self.len[q]: self.link[cur] q # 不用拆直接接上 else: # 克隆 q克隆点长度 len[p] 1关键不是 len[q] clone len(self.len) self.len.append(0) self.link.append(0) self.next.append(dict(self.next[q])) self.cnt.append(0) self.real.append(False) # 克隆点不是实点cnt 初值 0 self.len[clone] self.len[p] 1 self.link[clone] self.link[q] while p ! -1 and self.next[p].get(c) q: self.next[p][c] clone p self.link[p] self.link[q] clone self.link[cur] clone self.last cur def build_cnt(self): 幂等先重置 cnt再按 len 从大到小parent 树拓扑序累加。 self.cnt [1 if r else 0 for r in self.real] order sorted(range(len(self.len)), keylambda x: -self.len[x]) for v in order: if self.link[v] ! -1: self.cnt[self.link[v]] self.cnt[v] def distinct_substrings(self) - int: 本质不同子串个数不需要 cnt。 return sum(self.len[v] - self.len[self.link[v]] for v in range(1, len(self.len))) def longest_repeat(self) - int: 最长出现 ≥2 次的子串长度。 self.build_cnt() return max((self.len[v] for v in range(1, len(self.len)) if self.cnt[v] 2), default0) def occur(self, t: str) - int: 查询子串 t 的出现次数每处起止位置都算一次。 v 0 for c in t: if c not in self.next[v]: return 0 v self.next[v][c] self.build_cnt() return self.cnt[v] if __name__ __main__: S ababa sam SAM(S) print(呼号串:, S) print(本质不同子串个数:, sam.distinct_substrings()) # 9 print(最长重复片段长度:, sam.longest_repeat()) # 3 (aba) print(出现次数 occur(aba):, sam.occur(aba)) # 2 print(出现次数 occur(abab):, sam.occur(abab)) # 1 print(出现次数 occur(abc):, sam.occur(abc)) # 03.5 C 完整实现#include iostream #include vector #include string #include map #include algorithm using namespace std; struct State { int len; // 该状态代表的最长子串长度 int link; // 后缀链接parent 树父节点根节点为 -1 mapchar, int next; // 转移字符 - 状态编号 int cnt; // endpos 集合大小出现次数 bool real; // 实点真实前缀状态才初始 cnt1 State(int l 0, int ln -1, bool r false) : len(l), link(ln), cnt(0), real(r) {} }; struct SAM { vectorState st; int last; SAM() { st.emplace_back(0, -1, false); // 状态 0空串根非实点 last 0; } void extend(char c) { int cur (int)st.size(); st.emplace_back(0, 0, true); // 新整串前缀 实点 st[cur].len st[last].len 1; // 新状态长度 上一整串长度 1 int p last; while (p ! -1 !st[p].next.count(c)) { st[p].next[c] cur; p st[p].link; } if (p -1) { st[cur].link 0; } else { int q st[p].next[c]; if (st[p].len 1 st[q].len) { st[cur].link q; } else { int clone (int)st.size(); st.emplace_back(st[p].len 1, st[q].link, false); // 克隆点非实点 st[clone].next st[q].next; while (p ! -1 st[p].next.count(c) st[p].next[c] q) { st[p].next[c] clone; p st[p].link; } st[q].link clone; st[cur].link clone; } } last cur; } void build_cnt() { // 幂等先重置 cnt再按 len 从大到小累加 for (auto s : st) s.cnt s.real ? 1 : 0; vectorint order(st.size()); for (int i 0; i (int)st.size(); i) order[i] i; sort(order.begin(), order.end(), [](int a, int b) { return st[a].len st[b].len; }); for (int v : order) if (st[v].link ! -1) st[st[v].link].cnt st[v].cnt; } long long distinct_substrings() { long long ans 0; for (int v 1; v (int)st.size(); v) ans st[v].len - st[st[v].link].len; return ans; } int longest_repeat() { build_cnt(); int best 0; for (int v 1; v (int)st.size(); v) if (st[v].cnt 2) best max(best, st[v].len); return best; } int occur(const string t) { int v 0; for (char c : t) { if (!st[v].next.count(c)) return 0; v st[v].next[c]; } build_cnt(); return st[v].cnt; } }; int main() { string S ababa; SAM sam; for (char c : S) sam.extend(c); cout 呼号串: S endl; cout 本质不同子串个数: sam.distinct_substrings() endl; // 9 cout 最长重复片段长度: sam.longest_repeat() endl; // 3 cout occur(\aba\): sam.occur(aba) endl; // 2 cout occur(\abab\): sam.occur(abab) endl; // 1 cout occur(\abc\): sam.occur(abc) endl; // 0 return 0; }3.6 样例运行结果以呼号串S ababa为例本质不同子串个数: 9 最长重复片段长度: 3 aba 出现 2 次 occur(aba): 2 occur(abab): 1 occur(abc): 0验证一下长度为 1 的不同子串有a,b2 个长度 2 有ab,ba2 个长度 3 有aba,bab2 个长度 4 有abab,baba2 个长度 5 有ababa1 个。合计22221 9与程序输出一致。重复片段里aba在第 0–2 位和第 2–4 位各出现一次长度 3 是最长的完美吻合。四、易错点提醒新状态长度 len[last] 1绝不是len数组的当前下标cur。一旦把长度误写成状态编号只要出现过克隆节点编号就不再等于前缀长度整棵结构会错位、计数全错——这是最隐蔽也最致命的坑。克隆点长度 len[p] 1不是len[q]。写成len[q]会让link树不再满足子节点 len 严格大于父节点cnt累加顺序直接乱掉。克隆点必须标记为非实点cnt初值 0只有真正由extend新建的整串前缀才是实点cnt 1。漏标会让出现次数整体虚高。cnt累加必须按len从大到小即 parent 树的拓扑序。子节点先于父节点汇总父节点才能拿到全部子孙的贡献。把build_cnt写成幂等先重置再累加多次调用也不必担心计数被重复叠加。根节点的link设为-1循环条件用while p ! -1。若误设成0当终止标志会让p0提前退出、转移没接全。字符集用map/dict而非大数组。题目若限定小写字母可开 26 大小数组提速但多字符集中文、Unicode必须用映射否则爆内存。五、进阶方向广义后缀自动机多串把多份呼号合并管理时在 Trie 上建 SAM或用分隔符拼接可同时统计跨串的子串信息注意多串cnt初始要按贡献来自哪几个串分别打标记。两串最长公共子串对串S建 SAM让T在上面跑——走不动就沿link回跳并缩短当前匹配长度全程O(|T|)经典模板题。字典序第 k 小子串SAM 本质是一张 DAG先统计从每个状态出发的路径总数再按字符序贪心走k步对应「弦论」类题目。与后缀数组 / 后缀树对比后缀数组靠rank和height也能做很多子串题但 SAM 在建图后查询更在线理解两者关系能让你在考场上灵活选型。结合 LCP / 子串统计综合题如本质不同子串的总长度第 k 小子串的具体串内容等都是在今天骨架上的自然延伸。六、小结与互动后缀自动机用状态最少化的思想把O(|S|²)的子串世界压缩进了O(|S|)的状态空间。记住三句话就能上手extend增量建机、clone保最小、cnt沿link倒序汇总。它既是子串计数、重复检测、模式串查询的瑞士军刀也是通往广义 SAM、最长公共子串、字典序第 k 子串等省选真题的必经之路。互动时间如果广播台的呼号串是S aabaa请你手算或跑一下代码看看本质不同子串个数和最长重复片段长度分别是多少把你的答案留在评论区我们一起对一对也欢迎说说你在字符串题上踩过的最离谱的坑。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。