在第34篇中，KMP算法以 O(n+m)O(n+m) 的时间完成了单次模式匹配。但如果同一个文本需要面对数百万次不同的查询，每次查询都用KMP扫描一遍文本显然不现实。数据库领域的核心智慧是“为数据建立索引以加速查询”，字符串领域同样如此。后缀树和后缀数组正是字符串索引结构的两大基石——它们在预处理阶段对文本进行组织，使得任意长度 mm 的模式串可以在 O(m)O(m) 或 O(mlogn)O(mlogn) 的时间内完成匹配，且匹配时间与文本长度 nn 无关。
一、后缀树：定义、功能与朴素构造
给定长度为 nn 的字符串 SS，其后缀树是一棵压缩字典树，包含了 SS 的所有 nn 个后缀。形式化地，后缀树是一棵有根树，满足以下性质：
每条边上标记有 SS 的一个非空子串，且同一顶点出发的各边的首字符互不相同。
从根到任意叶节点的路径恰好拼出 SS 的某个后缀，每个叶节点唯一对应一个后缀。
任意内部节点至少有 22 个子节点（压缩性质——无单分支节点）。
为处理边界，通常在 SS 末尾添加一个不在字母表中的终止符 $$$。这使得任意后缀都不可能成为其他后缀的前缀，从而保证了叶节点与后缀的一一对应。
后缀树的存在性是显然的——最多 nn 个后缀，每个后缀长度不超过 nn，总字符数 O(n2)O(n2)。但通过压缩路径（将单分支链压缩为一条边），后缀树的节点数被压缩至 O(n)O(n)：内部节点均为分支点，数量不超过 n−1n−1；叶节点恰为 nn 个；总节点数不超过 2n2n。每条边上的标记无需显式存储原字符串，仅存储起始和终止索引即可，因此总空间为 O(n)O(n)。
朴素构造算法——逐个后缀插入压缩字典树——的时间为 O(n2)O(n2)，因为每个后缀的平均长度为 O(n)O(n)，插入操作可能遍历大量已有边。
二、Ukkonen算法：线性时间在线构造
Esko Ukkonen于1995年提出的算法以后缀树的在线线性构造载入史册。所谓“在线”，即从左到右逐个扩展 SS 的前缀，在每步追加一个字符后增量式地更新后缀树。算法整体复杂度为 O(n)O(n)。
Ukkonen算法的核心是维护一系列活动点，记录当前仍需扩展的位置。它的执行过程以 SS 的每个字符为阶段，逐阶段扩展。第 ii 个阶段处理字符 S[i]S[i]，目标是将所有从根出发对应 S[1..i]S[1..i] 的某个后缀的路径延伸至包含 S[i]S[i]。
关键优化有三项，缺一则无法达到线性时间。
后缀链接是从一个内部节点指向另一个内部节点的指针，它连接“去掉首字符”的后缀在树中的对应位置。具体而言，若某内部节点的路径标记为 awaw（aa 为单字符），则其后缀链接指向路径标记为 ww 的节点。后缀链接使得算法在完成一个后缀的扩展后，能快速跳转到下一个需扩展的位置，而无需从根重新遍历。
单次扩展的惰性处理：在某一阶段中，当某次扩展发现所需字符已存在于当前边的下一位置时，该后缀及所有更短后缀的扩展均已完成（规则3），本阶段可以提前终止。这保证了每个阶段内实际执行的扩展操作次数的期望极小。
全局边索引：所有边上的标记以 (start,end)(start,end) 索引对形式存储，其中 endend 可以是一个全局指针，指向“当前阶段结尾”。新增字符时无需逐边更新标记，仅需推进全局指针即可。
Ukkonen算法的时间复杂度通过平摊分析严格证明为 O(n)O(n)。nn 个阶段中，每次成功的边延伸耗时常数，后缀链接跳转的总次数受限于树的大小，而“沿树向下遍历”的总步数受限于树的深度变化。完整证明涉及三项操作的分别平摊，但直觉上核心在于：每一步要么消耗一个待处理的后缀，要么沿树向下推进，每种操作的总次数均为 O(n)O(n)。
三、后缀数组：从概念到构造
后缀树功能强大但实现复杂，在实际工程中，更常使用的是其紧凑替代品——后缀数组。后缀数组 SA[0..n−1]SA[0..n−1] 是 SS 的所有后缀按字典序排序后的起始位置列表。即 SA[0]SA[0] 是字典序最小的后缀的起始索引，SA[1]SA[1] 是次小后缀的起始索引，依此类推。
后缀数组本身仅需一个整数数组，空间较后缀树的指针结构大幅减少。但仅有 SASA 还不够——为了将模式匹配从 O(mlogn)O(mlogn)（在后缀数组上二分查找）优化到 O(m)O(m)，还需附加高度数组 LCPLCP（Longest Common Prefix）记录相邻后缀的最长公共前缀长度。SASA 配合 LCPLCP 即构成后缀数组的增强版本，在功能上等价于后缀树。
后缀数组的构造算法经历了从 O(nlogn)O(nlogn) 到 O(n)O(n) 的发展历程。两种主流方法是倍增法和DC3算法。
倍增法基于“排名”的迭代倍增。初始时对所有长度为 11 的子串（单字符）按字符大小排名。此后第 kk 轮中，每个后缀的排序键值是二元组 (rank[i],rank[i+2k])(rank[i],rank[i+2k])，即前 2k2k 个字符的排名和接着的 2k2k 个字符的排名。对二元组进行基数排序，得到长度 2k+12k+1 的排序结果。由于每次倍增排序长度翻倍，至多 ⌈logn⌉⌈logn⌉ 轮即可完成。每轮排序用基数排序实现 O(n)O(n)，总复杂度 O(nlogn)O(nlogn)。倍增法实现相对简单，是算法竞赛中最常用的后缀数组构造方法。
DC3算法（也称Skew算法）实现了真正的线性时间 O(n)O(n)。其核心是分治：将后缀按起始位置模3余数分为三类（模3余0、余1、余2）。对非零余数的后缀进行特殊编码，递归调用DC3自身求解，得到其排序；然后利用该结果通过一次合并排序得到余0后缀的排序；最后将两部分有序序列合并。DC3的递归式为 T(n)=T(2n/3)+O(n)T(n)=T(2n/3)+O(n)，解得 T(n)=O(n)T(n)=O(n)。DC3的空间开销和常数因子均大于倍增法，但在 nn 极大（如数十亿字符的全基因组）时其线性优势具有决定意义。
四、时空效率与应用场景的比较
在空间占用方面，后缀数组仅需一个整数数组 SASA（4n4n 字节），加上可选的 LCPLCP 数组，总空间通常为 8n8n 到 12n12n 字节。而后缀树每个节点需存储多个指针（子节点指针、后缀链接、边的起止索引），即便采用优化表示，空间通常是后缀数组的数倍。
在构造时间方面，Ukkonen算法和后缀数组的DC3均为理论线性。但在实际运行中，倍增法因常数小且内存访问模式友好，对百万级以下的字符串往往快于DC3和Ukkonen实现。
在查询效率方面，后缀树支持 O(m)O(m) 的模式匹配——从根出发沿树下降，路径唯一。后缀数组需配合二分查找完成匹配，纯二分查找复杂度 O(mlogn)O(mlogn)；配合 LCPLCP 信息后可通过加速二分降至 O(m+logn)O(m+logn)。在需要大量短模式查询的场景（如搜索引擎补全），后缀树的 O(m)O(m) 查询具有理论优势。
在功能扩展方面，后缀树支持更丰富的操作：最长公共子串、最长回文子串、最小表示法等问题在后缀树上均有直接的线性解法。后缀数组配合 LCPLCP 数组和RMQ（区间最小值查询）预处理，能实现等价的功能，但实现复杂度略高。
五、总结与展望
后缀树与后缀数组是字符串索引技术的双璧。后缀树以其直观的结构和 O(m)O(m) 的查询时间为理论分析提供了清晰的图模型；后缀数组则以其紧凑的存储和简洁的实现成为工程实践的首选。Ukkonen算法的后缀链接技巧展示了平摊分析在处理增量式构造中的威力，而DC3算法的分治递归则为线性时间后缀排序提供了严格的理论保证。
字符串算法的疆域远不止精确匹配与索引。当模式包含通配符、容许编辑错误或需要模糊匹配时，需要更复杂的模型。而将字符串问题的视角从一维序列推广到二维乃至高维模式，计算几何的方法便开始登场。下一篇，我们将进入计算几何的基础——凸包问题的分治与扫描线解法，开启平面点集算法的新篇章。
