> For the complete documentation index, see [llms.txt](https://datastructure-1.gitbook.io/datastructure-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://datastructure-1.gitbook.io/datastructure-docs/di-ba-bu-fen-gao-ji-zi-fu-chuan/15-suffix-tree-and-array.md). # 第 15 章：后缀树与后缀数组 [<- 第 14 章　排序算法](/datastructure-docs/di-qi-bu-fen-pai-xu/14-sorting-algorithms.md) | [课程目录](/datastructure-docs/readme.md) | [附录 A：数据结构选择速查 ->](/datastructure-docs/fu-lu/appendix-a-quick-reference.md) > 所属模块：第八部分：高级字符串\ > 对应实现：suffixtree.cpp / suffixarray.cpp ### 本章导航 * [15.1 全文本索引的核心公理：子串即后缀的前缀](#c15-15-1) * [15.2 后缀树（Suffix Tree）：压缩 Trie 的几何进化](#c15-15-2) * [15.2.1 从 O(n²) 后缀 Trie 到 O(n) 后缀树的边压缩](#c15-15-2-1) * [15.2.2 终止符 $ 的关键作用与节点数上界证明](#c15-15-2-2) * [15.3 Ukkonen 算法 O(n) 在线构建核心秘籍](#c15-15-3) * [15.3.1 活动点（Active Point）三元状态机](#c15-15-3-1) * [15.3.2 后缀链接（Suffix Link）的虫洞跳转](#c15-15-3-2) * [15.3.3 扩展三规则（Rule 1 / 2 / 3）与提前终止](#c15-15-3-3) * [15.4 后缀数组（Suffix Array, SA）：紧凑内存的工程典范](#c15-15-4) * [15.4.1 SA 数组与 Rank 数组的互逆映射](#c15-15-4-1) * [15.4.2 倍增算法（Doubling Algorithm）构建原理](#c15-15-4-2) * [15.5 最长公共前缀（LCP）与 Kasai 算法 O(n) 线性推导](#c15-15-5) * [15.5.1 Kasai 不变量：height\[rank\[i\]\] >= height\[rank\[i-1\]\] - 1 的严格证明](#c15-15-5-1) * [15.5.2 线性扫描代码实现](#c15-15-5-2) * [15.6 四大经典字符串难题的 SA + LCP 妙解](#c15-15-6) * [15.6.1 单/多模式串快速匹配（二分查找）](#c15-15-6-1) * [15.6.2 最长重复子串（LRS）](#c15-15-6-2) * [15.6.3 两串最长公共子串（LCS，分隔符拼接法）](#c15-15-6-3) * [15.6.4 本质不同子串计数公式推导](#c15-15-6-4) * [15.7 后缀树 vs 后缀数组：理论巅峰与工程实用的对决](#c15-15-7) * [本章小结](#c15-summary) * [思考题与经典大厂面试题](#c15-exercises) *** ## 第 15 章　后缀树与后缀数组 > 难度：★★★★★ | 代码：[suffixtree.cpp](https://github.com/Huo0077/DataStructure/blob/main/suffixtree.cpp) / [suffixarray.cpp](https://github.com/Huo0077/DataStructure/blob/main/suffixarray.cpp) **前置知识**：[第 4 章](/datastructure-docs/di-san-bu-fen-chuan/04-string-matching-kmp.md) 字符串匹配思想，[第 5 章](/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/05-binary-tree-basics.md) 树的遍历，[第 14 章](/datastructure-docs/di-qi-bu-fen-pai-xu/14-sorting-algorithms.md) 基数排序与快速排序。 **学习目标**： 1. 理解“子串等于某个后缀的前缀”这一全文本索引第一性原理； 2. 掌握后缀树通过边压缩将空间从 (O(n^2)) 降维至 (O(n)) 的机制； 3. 掌握 Ukkonen 算法中“活动点、后缀链接、三类扩展规则”的在线更新机制； 4. 熟练掌握后缀数组（SA）的倍增构造法与二分匹配算法； 5. 掌握 Kasai 算法的核心不等式证明，并在 (O(n)) 线性时间内解决最长重复子串与本质不同子串计数问题。 *** ### 15.1 全文本索引的核心公理：子串即后缀的前缀 在文本检索和生物信息学（如人类基因组 30 亿对碱基的比对）中，我们面临一个核心挑战：**主文本 (T) 极其庞大且固定，而查询模式串 (P) 会到来成千上万次**。\ 若每次都用 KMP 从头扫描文本，单次查询需 (O(n))，成本高昂。我们必须对主文本 (T) 进行预处理，建立**全文本索引（Full-Text Index）**。 > **全文本索引的核心公理**：\ > **文本串 (T) 的任意一个子串（Substring），必然是 (T) 的某个后缀（Suffix）的前缀（Prefix）！** ``` 以 T = "banana" 为例: 所有的 6 个后缀为: 后缀 0: "banana" 后缀 1: "anana" 后缀 2: "nana" 后缀 3: "ana" 后缀 4: "na" 后缀 5: "a" 考察任意子串: 子串 "nan" ───> 正好是 后缀 2 ("nana") 的前 3 个字符! 子串 "ana" ───> 正好是 后缀 1 ("anana") 的前 3 个字符，也是后缀 3 ("ana") 的前 3 个字符! ``` **数学结论**：只要我们构建了一种能够高效检索所有后缀前缀的数据结构，**就等于在同一瞬间解决了该文本上所有可能的子串查询问题！** *** ### 15.2 后缀树（Suffix Tree）：压缩 Trie 的几何进化 #### 15.2.1 从 O(n²) 后缀 Trie 到 O(n) 后缀树的边压缩 最直观的方法是将 (T) 的所有后缀全部插入到一棵字典树（Trie）中，称为**后缀 Trie**： * **致命缺陷**：若 (T = \text{"a}^n \text{b}^n\text{"})，后缀 Trie 的节点总数将高达 (O(n^2))！对于 100KB 的文本，节点数突破 100 亿，内存直接崩溃！ 1973 年 Weiner 与 1976 年 McCreight 提出了**后缀树（Suffix Tree）**，引入了**路径压缩（Path Compression）**： * **压缩单分支路径**：将所有没有分支的单链内部节点全部抹除，将一整串连续字符合并为一条复合边； * **边上的区间表示**：边上不存储真实的字符串拷贝，而是仅存储一个下标二元组 `[start, end]`，代表子串 (T\[\text{start} .. \text{end}])，边开销恒定为 (O(1))！ ``` 【后缀 Trie (节点数爆棚 O(n²))】 【后缀树 (压缩单分支，节点数 <= 2n)】 root root / / b [0, 5] ("banana$") / / a Leaf 0 / n / a ... ``` #### 15.2.2 终止符 $ 的关键作用与节点数上界证明 在构建后缀树时，**必须在文本串末尾追加一个从未在文本中出现过的独特字符（通常为 `$`）**： * **作用**：防止某个后缀恰好是另一个较长后缀的前缀（例如 `"an"` 与 `"banana"`），导致该较短后缀停留在内部节点而无法到达叶子；追加 `$` 后，所有后缀两两互不为前缀，**每个后缀必然唯一对应树中的一个叶子节点**！ **节点数上界定理：** * 包含 (n) 个字符的字符串（含 `$`），恰好有 (n) 个叶子节点； * 在压缩树中，**每个内部节点至少拥有 2 个孩子**（度 (\ge 2)）； * 根据二叉/多叉树性质，拥有 (n) 个叶子且每个分支至少 2 度的树，其内部节点数至多为 (n - 1)； * **结论**：**整棵后缀树的节点总数绝对不会超过 (2n - 1)，空间复杂度严格为 (O(n))！** *** ### 15.3 Ukkonen 算法 O(n) 在线构建核心秘籍 1995 年 Esko Ukkonen 发表了著名的在线线性时间后缀树构建算法。算法从左到右逐个字符推进，维护一个不变量：**在第 (i) 步结束时，成功构建出前缀 (T\[0..i]) 的隐式后缀树**。 #### 15.3.1 活动点（Active Point）三元状态机 算法绝不从根节点重复扫描，而是维护一个\*\*活动点（Active Point）\*\*三元组： \[ \text{ActivePoint} = (\text{active\_node}, \text{active\_edge}, \text{active\_length}) ] * `active_node`：当前插入操作发生的基准节点； * `active_edge`：当前正沿着哪一条以该字符开头的出边向下走； * `active_length`：在当前出边上已经深入了几个字符的距离。 #### 15.3.2 后缀链接（Suffix Link）的虫洞跳转 若某个内部节点 (v) 代表子串 (x\alpha)（(x) 为单个字符，(\alpha) 为子串），则 (v) 的**后缀链接（Suffix Link）** 指向代表子串 (\alpha) 的内部节点。 * **作用**：当在节点 (v) 分裂创建新叶子后，**无需回到树根重新下潜**，直接顺着后缀链接像“穿越虫洞”一样以 (O(1)) 跳转到对应节点，继续执行下一个后缀的插入！ #### 15.3.3 扩展三规则（Rule 1 / 2 / 3）与提前终止 在处理新字符 (T\[i]) 时： * **Rule 1（叶子延伸）**：当前路径到达了某个叶子，直接将边末尾的 `end` 推进（在代码中通过全局指针变量实现 (O(1)) 批量隐式延伸）； * **Rule 2（分裂建点）**：当前路径上没有新字符 (T\[i])，在此处把边切断，**分裂出一个新的内部节点，并分出一条通往新叶子的分支**； * **Rule 3（字符已存在 / 提前终止！）**：当前路径上**已经存在新字符 (T\[i])**！这意味着后续所有更短的后缀此前也必然已经存在，**本次阶段直接提前终止！** 将未插入的计数累积到 `remainder`，立即进入下一个字符！正是 Rule 3 赋予了 Ukkonen 算法惊人的 (O(n)) 线性性能！ *** ### 15.4 后缀数组（Suffix Array, SA）：紧凑内存的工程典范 尽管后缀树理论完美，但其每个节点包含多个子指针、区间边界和后缀链接，指针开销巨大（在 64 位机器上每个字符通常占用 20\~40 字节内存）。\ 1990 年 Manber 和 Myers 提出了**后缀数组（Suffix Array, SA）**，将树形结构彻底拍扁为一个纯粹的 32 位整型数组！ #### 15.4.1 SA 数组与 Rank 数组的互逆映射 * **`sa[i]`**：将字符串 (S) 的所有 (n) 个后缀按**字典序升序排列**后，排在第 (i) 名的后缀在原字符串中的起始下标； * **`rank[k]`**：起始于下标 (k) 的后缀在字典序中的**排名（名次）**。 * **互逆不变量**： \[ \text{sa}\[\text{rank}\[i]] = i \quad \text{且} \quad \text{rank}\[\text{sa}\[k]] = k ] ``` 字符串 S = "banana" (长度 6): 下标与对应后缀: 0: banana 1: anana 2: nana 3: ana 4: na 5: a 字典序升序排列: 名次 0: "a" (原下标 5) 名次 1: "ana" (原下标 3) 名次 2: "anana" (原下标 1) 名次 3: "banana" (原下标 0) 名次 4: "na" (原下标 4) 名次 5: "nana" (原下标 2) 故后缀数组 sa = [5, 3, 1, 0, 4, 2] 名次数组 rank = [3, 2, 5, 1, 4, 0] (例如原下标 0 的 "banana" 排在第 3 名) ``` #### 15.4.2 倍增算法（Doubling Algorithm）构建原理 若直接对 (n) 个后缀进行快排，每次字符串比较耗时 (O(n))，总体需 (O(n^2 \log n))。\ **倍增思想（Manber-Myers）**： * 第 1 轮：按长度为 1 的前缀排序； * 第 2 轮：利用第 1 轮排名的结果，两两拼装成长度为 2 的关键字进行双关键字排序； * 第 (k) 轮：已知长度为 (2^{k-1}) 的排名，将后缀 (i) 的前 (2^k) 个字符拆分为： * 第一关键字：前半段长度 (2^{k-1}) 的排名 (\text{rank}\[i])； * 第二关键字：后半段长度 (2^{k-1}) 的排名 (\text{rank}\[i + 2^{k-1}])。 * 借助基数排序，每轮排序只需 (O(n))；总共倍增 (\lceil \log\_2 n \rceil) 轮，**整体以极高常数因子在 (O(n \log n)) 时间内完成构建！** *** ### 15.5 最长公共前缀（LCP）与 Kasai 算法 O(n) 线性推导 仅有 `sa` 数组只能做模式二分查找。要让后缀数组具备与后缀树完全等价的能力，必须引入**高度数组（Height / LCP 数组）**！ **定义**： * (\text{lcp}(A, B)) 表示字符串 (A) 和 (B) 的最长公共前缀长度； * **`height[i]`** 表示在排好序的后缀数组中，**第 (i) 个后缀与第 (i-1) 个后缀的最长公共前缀长度**： \[ \text{height}\[i] = \text{lcp}(S\[\text{sa}\[i]..n-1], S\[\text{sa}\[i-1]..n-1]) ] #### 15.5.1 Kasai 不变量：height\[rank\[i]] >= height\[rank\[i-1]] - 1 的严格证明 2001 年 Kasai 等人提出了一个震惊算法界的定理： > **Kasai 核心定理**：\ > 设 (h\[i] = \text{height}\[\text{rank}\[i]])，即从原串下标 (i) 开始的后缀与其在字典序中前一名后缀的 LCP 长度。则必有： \[ h\[i] \ge h\[i - 1] - 1 ] **严格推导证明：** 1. 设排在后缀 (i - 1) 前一名的后缀为 (k)（即 (\text{rank}\[k] = \text{rank}\[i - 1] - 1)）； 2. 它们的公共前缀长度为 (h\[i - 1])； 3. 若 (h\[i - 1] \le 1)，不等式 (h\[i] \ge 0) 自然恒成立； 4. 若 (h\[i - 1] > 1)，说明后缀 (i - 1) 和后缀 (k) 具有至少 2 个相同的公共前缀字符： * 后缀 (i - 1) 的形式为：(c \alpha \dots) * 后缀 (k) 的形式为：(c \alpha \dots)（其中 (c) 是单个字符，(\alpha) 长度为 (h\[i - 1] - 1)）； 5. 同时抹去首字符 (c)： * 后缀 (i - 1) 变为后缀 (i = \alpha \dots) * 后缀 (k) 变为后缀 (k + 1 = \alpha \dots) 6. 因为在字典序中 (k < i - 1)，且首字符相同，抹去首字符后依然有：(\text{后缀 } k + 1 < \text{后缀 } i)； 7. 此时后缀 (k + 1) 与后缀 (i) 的公共前缀长度至少为 (h\[i - 1] - 1)； 8. 而在字典序中排在后缀 (i) 正好紧挨着的前一名后缀，其与后缀 (i) 的 LCP **只会比后缀 (k+1) 更长，绝不可能变短**！ 9. 故必有：(h\[i] \ge h\[i - 1] - 1)！证毕！■ #### 15.5.2 线性扫描代码实现 ```cpp std::vector buildHeight(const std::string& s, const std::vector& sa, const std::vector& rank) { int n = s.size(); std::vector height(n, 0); int h = 0; // 当前 lcp 长度 for (int i = 0; i < n; ++i) { if (rank[i] == 0) { h = 0; continue; } int j = sa[rank[i] - 1]; // 字典序中紧邻的前一名后缀 if (h > 0) --h; // 利用 Kasai 定理: 下限至少为 h - 1 while (i + h < n && j + h < n && s[i + h] == s[j + h]) { ++h; } height[rank[i]] = h; } return height; } ``` > **复杂度分析**：`h` 最多增加 (n) 次，每次循环最多减少 1（最多减 (n) 次）。故 `while` 内的字符比对总次数绝对不超过 (2n)，**计算全套 Height 数组严格为 (O(n))！** *** ### 15.6 四大经典字符串难题的 SA + LCP 妙解 #### 15.6.1 单/多模式串快速匹配（二分查找） 在 `sa` 数组上对模式串 (P) 进行二分查找。由于所有后缀在 `sa` 中是严格字典序排列的，只需 (O(|P| \log n)) 即可找到匹配区间的左右边界。配合 RMQ（区间最值查询）加速 LCP，可进一步优化至 (O(|P| + \log n))！ #### 15.6.2 最长重复子串（LRS） **问题**：求字符串中至少出现两次的最长子串。\ **解法**：出现在两处的子串，必然是两个不同后缀的公共前缀。最长公共前缀必定出现在字典序相邻的两项之间！因此，**(\max(\text{height}\[i])) 即为全串最长重复子串的长度**！ #### 15.6.3 两串最长公共子串（LCS，分隔符拼接法） **问题**：求字符串 (A) 和 (B) 的最长公共子串。\ **解法**：用未出现过的符号 `#` 拼接两串：(S = A + \text{"#"} + B)。计算 (S) 的 `sa` 和 `height`。遍历 `height` 数组，**寻找满足 (\text{sa}\[i]) 与 (\text{sa}\[i-1]) 分别来自不同原串（一个小于 (|A|)，一个大于 (|A|)）的最大 (\text{height}\[i])**！ #### 15.6.4 本质不同子串计数公式推导 字符串 (S) 的全部非空子串总数上限为 (\frac{n(n+1)}{2})。每个后缀 (\text{sa}\[i]) 贡献 (n - \text{sa}\[i]) 个前缀子串。其中，与前一个后缀重复的前缀个数恰好是 (\text{height}\[i])！\ **去重后的本质不同子串总数公式**： \[ \text{TotalUniqueSubstrings} = \frac{n(n + 1)}{2} - \sum\_{i=1}^{n-1} \text{height}\[i] ] *** ### 15.7 后缀树 vs 后缀数组：理论巅峰与工程实用的对决 | 比较维度 | 后缀树 (Suffix Tree) | 后缀数组 (Suffix Array) | | ------------ | ----------------------------- | --------------------------------------- | | **内存开销** | (O(n))，每个字符约占 20\~40 字节（指针繁多） | **(O(n))，每个字符仅需 4 字节（极度紧凑）** | | **CPU 缓存表现** | 差（指针跳转引发高频 Cache Miss） | **极优（纯一维数组连续存储，预取友好）** | | **构建复杂度** | (O(n))（Ukkonen 算法） | (O(n \log n))（倍增）或 (O(n))（SA-IS 算法） | | **代码实现难度** | 极高（状态机与后缀链接极其繁复） | 中等（倍增基数排序易于调试与模板化） | | **模式查询时间** | (O(m)) 沿树下潜 | (O(m \log n)) 二分查找（工程中常数极小） | | **工业界现状** | 偏向理论研究 | **工业界与算法竞赛绝对事实标准**（如 BWT 算法、BWA 基因比对工具） | *** ### 本章小结 1. **第一性原理的威力**：子串即后缀之前缀，统摄了全文本子串检索的万千变式。 2. **边压缩的巧夺天工**：后缀树通过区间二元组替代显式字符串拷贝，将爆炸的平方级空间降维为严格线性。 3. **Ukkonen 的状态转移**：活动点记忆上下文，后缀链接实现跨越式转移，Rule 3 赋予了提前剪枝的生命力。 4. **Kasai 不等式的优雅**：(h \ge h-1) 巧妙利用了相邻后缀去掉首字符后的单调有序性，以最朴素的双指针实现了 (O(n)) 线性计算。 *** ### 思考题与经典大厂面试题 1. **后缀自动机（SAM, Suffix Automaton）**：后缀自动机是能够接受字符串所有后缀的最小确定有限状态自动机（DFA）。相比后缀树，SAM 在状态转移和时空开销上有何独到优势？ 2. **最长回文子串的后缀数组解法**：如何将原串 (S) 与其翻转串 (S^R) 用特殊字符 `#` 拼接，通过后缀数组的 LCP 快速在 (O(n \log n)) 时间内找出最长回文子串？ 3. **手算演练**：对于字符串 (S = \text{"ababa"})，请手工写出其所有后缀、`sa` 数组、`rank` 数组和 `height` 数组，并据此计算其本质不同的子串个数。