在第34篇中KMP算法以 O(nm)O(nm) 的时间完成了单次模式匹配。但如果同一个文本需要面对数百万次不同的查询每次查询都用KMP扫描一遍文本显然不现实。数据库领域的核心智慧是“为数据建立索引以加速查询”字符串领域同样如此。后缀树和后缀数组正是字符串索引结构的两大基石——它们在预处理阶段对文本进行组织使得任意长度 mm 的模式串可以在 O(m)O(m) 或 O(mlog⁡n)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]。关键优化有三项缺一则无法达到线性时间。后缀链接是从一个内部节点指向另一个内部节点的指针它连接“去掉首字符”的后缀在树中的对应位置。具体而言若某内部节点的路径标记为 awawaa 为单字符则其后缀链接指向路径标记为 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(mlog⁡n)O(mlogn)在后缀数组上二分查找优化到 O(m)O(m)还需附加高度数组 LCPLCPLongest Common Prefix记录相邻后缀的最长公共前缀长度。SASA 配合 LCPLCP 即构成后缀数组的增强版本在功能上等价于后缀树。后缀数组的构造算法经历了从 O(nlog⁡n)O(nlogn) 到 O(n)O(n) 的发展历程。两种主流方法是倍增法和DC3算法。倍增法基于“排名”的迭代倍增。初始时对所有长度为 11 的子串单字符按字符大小排名。此后第 kk 轮中每个后缀的排序键值是二元组 (rank[i],rank[i2k])(rank[i],rank[i2k])即前 2k2k 个字符的排名和接着的 2k2k 个字符的排名。对二元组进行基数排序得到长度 2k12k1 的排序结果。由于每次倍增排序长度翻倍至多 ⌈log⁡n⌉⌈logn⌉ 轮即可完成。每轮排序用基数排序实现 O(n)O(n)总复杂度 O(nlog⁡n)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 极大如数十亿字符的全基因组时其线性优势具有决定意义。四、时空效率与应用场景的比较在空间占用方面后缀数组仅需一个整数数组 SASA4n4n 字节加上可选的 LCPLCP 数组总空间通常为 8n8n 到 12n12n 字节。而后缀树每个节点需存储多个指针子节点指针、后缀链接、边的起止索引即便采用优化表示空间通常是后缀数组的数倍。在构造时间方面Ukkonen算法和后缀数组的DC3均为理论线性。但在实际运行中倍增法因常数小且内存访问模式友好对百万级以下的字符串往往快于DC3和Ukkonen实现。在查询效率方面后缀树支持 O(m)O(m) 的模式匹配——从根出发沿树下降路径唯一。后缀数组需配合二分查找完成匹配纯二分查找复杂度 O(mlog⁡n)O(mlogn)配合 LCPLCP 信息后可通过加速二分降至 O(mlog⁡n)O(mlogn)。在需要大量短模式查询的场景如搜索引擎补全后缀树的 O(m)O(m) 查询具有理论优势。在功能扩展方面后缀树支持更丰富的操作最长公共子串、最长回文子串、最小表示法等问题在后缀树上均有直接的线性解法。后缀数组配合 LCPLCP 数组和RMQ区间最小值查询预处理能实现等价的功能但实现复杂度略高。五、总结与展望后缀树与后缀数组是字符串索引技术的双璧。后缀树以其直观的结构和 O(m)O(m) 的查询时间为理论分析提供了清晰的图模型后缀数组则以其紧凑的存储和简洁的实现成为工程实践的首选。Ukkonen算法的后缀链接技巧展示了平摊分析在处理增量式构造中的威力而DC3算法的分治递归则为线性时间后缀排序提供了严格的理论保证。字符串算法的疆域远不止精确匹配与索引。当模式包含通配符、容许编辑错误或需要模糊匹配时需要更复杂的模型。而将字符串问题的视角从一维序列推广到二维乃至高维模式计算几何的方法便开始登场。下一篇我们将进入计算几何的基础——凸包问题的分治与扫描线解法开启平面点集算法的新篇章。