核心概述
后缀树/后缀自动机以紧凑结构表示字符串的所有子串，在 O(n) 构建代价下支持存在性、出现次数、不同子串数与最长公共子串等查询，适配静态或增量场景。
原文引述
Description: Suffix tree (compressed trie of all suffixes) or suffix automaton (deterministic acyclic automaton for all substrings). Build O(n). Supports substring occurrence counting, distinct substrings, LCS, etc. Time: Build O(n); query O(|pattern|) for existence/occurrence Status: tested ——摘自本节点现有英文注释
展开阐述
-
定义与背景、典型适用场景
- 后缀树：所有后缀的压缩 Trie，边以原串区间 (start, end) 表示；空间线性，支持在线构建与显式后缀操作。
- 后缀自动机（SAM）：描述所有子串的确定性有向无环自动机；空间线性，增量构建，适用于多次查询与统计。
- 场景：静态全局分析（后缀树）；动态插入/多次查询（SAM）。
-
接口/字段/数据结构与输入输出语义（按仓库约定）
- SAM 典型结构（据约定风格）：
- Node:
- next：map<char,int>（或小字符集用数组）。
- link：后缀链接（suffix link）。
- len：状态对应的最长子串长度。
- 全局：初始状态 0，last=0。
- Node:
- 输出语义与统计：
- SAM 状态数 ≤ 2n−1；可通过 endpos 集合大小（拓扑序累加）统计出现次数；
- 不同子串数为 Σ (len[v] − len[link[v]])。
- SAM 典型结构（据约定风格）：
-
核心流程与关键要点
- SAM 扩展字符 c：
- 新建 cur，len[cur]=len[last]+1；
- 自 p=last 向前，若无 c 转移则补建，直到 p=−1 或遇到已有转移；
- 若 p=−1，link[cur]=0；否则令 q=next[p][c]：
- 若 len[p]+1 == len[q]：link[cur]=q；
- 否则克隆 q 为 clone：复制转移，len[clone]=len[p]+1，link[clone]=link[q]；令 q、cur 的 link 指向 clone，并自 p 向前重定向相关转移；
- last=cur。
- 主要查询：
- 子串存在性：沿 next 走模式串；中途缺失即不存在；
- 出现次数：预处理 endpos 大小（拓扑序累加）；
- 不同子串数：Σ (len[v] − len[link[v]])；
- 最长公共子串：建 SAM 后，在另一串上行走并维护最长匹配；
- 第 k 小子串：按 len/字典序遍历可生成序列。
- 后缀树（Ukkonen）要点：
- 边以原串区间存储；空间线性；支持在线构建；可直接得到全部后缀的显式表示。
- SAM 扩展字符 c：
-
复杂度与边界条件
- 构建：O(n)（均摊常数）；查询：存在性 O(|pattern|) 或在计数预处理后 O(1) 抽取统计。
- 边界：字符集映射需一致；内存线性增长，适合 n 规模较大的场景。
-
与相邻技术的取舍对比
- 与 124-字符串-后缀数组：SA 静态分析实现简洁；SAM 动态/多次查询更便捷。
- 与模式/回文类：单模式匹配参见 121-字符串-KMP、126-字符串-Z函数；
- 与指纹法：概率等价判定参见 119-字符串-字符串哈希；
- 多模式匹配可参考 118-字符串-AC自动机。