手头这本《Handbook of Data Structures and Applications》我翻得最多、折角最多的一章就是关于Suffix Trees和Suffix Arrays的部分。别看后缀树Suffix Trees和后缀数组Suffix Arrays这俩名字听起来像某个竞赛选手的私藏套路实际上它们是字符串处理领域里最能打的一套底层结构基因组序列比对、全文检索、数据压缩、自然语言处理里的最长公共子串背后全是它们在撑场面。这篇就把我啃这一章时的完整笔记、推导过程和踩坑经验整理出来适合正在学Data Structures进阶内容、准备面试算法题、或者做文本处理相关项目的朋友参考。1. 为什么后缀结构是字符串算法里的万能钥匙先聊个比较反直觉的事实很多看起来毫无关联的字符串问题比如一个字符串里出现次数最多的重复片段是什么两个超长DNA序列的公共部分有多长一段文本里有没有出现过某个模式串本质上都能归约成同一个操作——高效比较一堆字符串后缀之间的公共前缀。后缀树和后缀数组这两个数据结构就是为这个操作量身定做的。1.1 从朴素方法到后缀结构的思维跳跃假设你手里有一个长度为n的字符串S想找出它的最长重复子串。最笨的办法是枚举所有子串两两比较复杂度O(n³)甚至更高。稍微聪明一点的做法是枚举所有后缀因为任何一个子串都是某个后缀的前缀所以找重复子串等价于找两个后缀的最长公共前缀。但问题是一个长度为n的字符串有n个后缀两两比较还是O(n²)级别。对于人类基因组这种长度在30亿级别的输入这个复杂度等于没有算法。后缀树的核心思路就是把n个后缀一次性压进一棵树里让每次公共前缀比较的耗时从O(n)级别降下来。我第一次看到这个想法时觉得特别惊艳——它本质上是在用空间换时间把查询时反复比较字符串的代价转化为构建时一次性预处理的代价。1.2 Handbook这一章在整本书里的定位《Handbook of Data Structures and Applications》是一本非常工业级的参考书它不是ACM竞赛教材那种上来就丢定理的风格而是每个数据结构都讲清楚动机-定义-构建-应用-变种。后缀树和后缀数组这一章继承了这个特点前半部分用大量图例讲清楚后缀树到底长什么样后半部分花了不少篇幅讲后缀数组与LCPLongest Common Prefix最长公共前缀数组之间的关系。如果你和我一样是自学我强烈建议不要把这一章当小说一样从头读到尾而是先看目录搞清楚它把内容拆成了哪几块。Handbook这一章的逻辑大致是这样后缀树的定义与基本性质Ukkonen在线构建算法或者至少讲清楚为什么朴素构建不行后缀数组的定义与构建方法LCP数组及其在问题求解中的作用后缀树与后缀数组的等价转换实际应用案例我读下来的体会是这章的前三节是重中之重后面的内容基本都是在反复使用前三节建立起来的核心概念。1.3 这一章适合谁读、读之前需要什么基础如果你想把这一章真正啃下来我建议先具备三样东西熟悉Trie前缀树的插入与查询逻辑因为后缀树本质是一棵压缩过的后缀Trie理解分治法和倍增法的基本思想因为后缀数组的构建算法大量用到这些思路有一点耐心去推演边界条件比如处理空串、单字符、所有字符相同等特殊情况如果这三样都还没有建议先回去补补基础再来看这一章。不然很容易被Ukkonen算法那套活跃点剩余数的概念劝退。2. 后缀树到底是什么从Trie到压缩树的进化后缀树定义看起来很简单包含字符串S所有后缀的一棵压缩Trie。但这个定义里两个词都暗藏玄机——所有后缀和压缩。2.1 后缀是什么、为什么必须用终止符字符串S banana的后缀集合是bananaananananaananaa如果把这6个后缀直接插入一棵普通Trie你会得到一个后缀Trie。问题来了有些后缀是另一些后缀的前缀比如a是ana的前缀这样从根节点走到叶子节点的路径可能对应多个后缀树的叶子节点和后缀的对应关系就乱了。解决办法是在字符串末尾加一个字典序最小的唯一终止符比如$让每个后缀都以一个永不在字符串内部出现的字符结尾。于是S变成banana$后缀变成banana$anana$nana$ana$na$a$$——现在没有任何后缀是另一个后缀的前缀了每个后缀都恰好对应一条从根到叶子的路径。这个终止符看着不起眼但它解决了一个非常关键的问题确保每个后缀能被唯一地标识为一条根到叶子的路径。2.2 压缩Trie为什么必须把链压成边不加压缩的后缀Trie有一个致命问题插入n个后缀总节点数可以达到O(n²)。还是拿banana举例所有后缀共享了大量前缀但如果是abcdefg...这种没有公共前缀的字符串普通Trie里就会出现很多只有一个孩子的中间节点——它们只承担了传递的功能没有提供任何分叉信息。压缩Trie的做法很直接把只有一个孩子的节点直接合并到边上边上存的不再是单个字符而是一个子串。这样一棵树里每个内部节点都至少有2个孩子叶子节点的数量等于后缀数量n因此内部节点数不超过n-1整棵树的节点总数变成O(n)。这就是后缀树比后缀Trie强大的根本原因信息量一点没少但空间从O(n²)降到了O(n)。这种把链条压成边的思路在芬威克树、线段树的离散化等很多数据结构里都有类似的影子但后缀树是把它用到极致的地方。2.3 后缀树上怎么挂数据边标签与路径标签后缀树的每条边都携带一个子串标签从根节点到某个内部节点或叶子的路径上所有边标签拼接起来就是路径标签。如果这个路径标签恰好是S的某个后缀的前缀那么这个节点就对应字符串中的一个位置。Handbook里有几个非常容易混的概念我一开始看的时候被绕了好久边标签edge label边上存的子串在S中的起止位置路径标签path label从根到某节点的路径上所有边标签的拼接叶子节点对应一个唯一后缀内部节点对应一组后缀的公共前缀实现时一般不会真的在每条边上存一个字符串副本而是存两个整数坐标(start, end)指向S中的某个闭区间。这个优化非常关键它让后缀树的存储空间真正做到了O(n)而不是O(n²)。后面写代码实现时一定要记住这一点否则存字符串副本能把你内存打爆。2.4 后缀树的几个重要性质性质这东西光背结论没用最好能自己推一遍。我发现只要抓住下面三点后面看应用的时候就顺多了叶子节点数 n因为每个后缀对应一个叶子这是定义保证的。内部节点数 ≤ n-1每个内部节点至少2个孩子整棵树是满的full压缩树所以节点总数不超过2n-1。每个内部节点的路径标签都是S中出现过至少2次的子串这是公共前缀的直接推论也是用后缀树找重复子串的理论基础。这三条性质撑起了后缀树几乎所有应用场景。最长重复子串、最长公共子串、模式匹配全都是在这三条性质上做文章。3. Ukkonen构建算法在线构建后缀树的硬核之处后缀树的朴素构建法非常直观从S的第一个字符开始不断把新的后缀插入到树里。但这样做的总复杂度是O(n²)因为每次插入都可能要重新从根节点走一遍。对于n很大的情况这不能接受。Ukkonen算法把这个过程优化到了O(n)——而且它是在线的也就是从左到右扫描一遍S每读入一个字符就更新出当前前缀的后缀树。3.1 为什么朴素插入是O(n²)的假设已经建好了S[1..i]的后缀树现在要插入第i1个字符让树变成S[1..i1]的后缀树。从根开始需要找到新后缀应该挂在哪个位置。如果从根重新走一遍每次匹配一个字符都要比较平均要走O(n)步。i从1到n总复杂度O(n²)。这个复杂度对banana这种短字符串无所谓但对实际应用中几百万甚至上亿字符的文本完全不可行。所以Ukkonen才是后缀树构建里的主角。3.2 Ukkonen的核心思想后缀链接与活跃点Ukkonen算法引入了一堆让人头大的术语活跃点active point、剩余数remainder、后缀链接suffix link。我第一次看的时候满脑子都是这到底在干嘛。后来我找到了一种比较生活化的理解方式。想象你在一家甜品店排队队伍里的每个人代表一个需要被更新的后缀。每读入一个新字符队伍里所有人都要往前挪一步新后缀出现所有旧后缀都变长了。但你不必一次性处理所有人——Ukkonen算法的妙处就在于懒惰更新。它维护一个活跃三元组(active_node, active_edge, active_length)表示当前最新需要处理的后缀离正确位置还差多少步然后用剩余数remainder记录还有多少个后缀待插入。每次处理新字符时只需要从活跃点出发沿着活跃边往下走能走就走走不动了就拆边、建内部节点、连后缀链接。后缀链接相当于是树里的快捷方式它让从一条路径跳转到另一条路径变成O(1)操作而不是重新从根匹配。如果你觉得这些概念太抽象我的建议是先放下我一定要马上学会手写Ukkonen这个执念。很多教科书把这章列为核心是因为它是理论上的巅峰但实际工程中用后缀数组的倍增法或DC3算法更常见构建代码也更好写。理解Ukkonen的为什么在线为什么O(n)即可不一定要做到能默写。3.3 Handbook对Ukkonen的讲解特点Handbook这一章有个很贴心的设计它先讲了后缀树的定义和朴素构建然后才进入Ukkonen而且给出了不少图示。我不否认这本书的图示密度不如专题性论文但它好就好在把Ukkonen算法拆成了延伸extension这个原子操作。Ukkonen算法本质上做了n轮扩展第i轮读完S[i]之后对j从1到i把后缀S[j..i]加入树中。但暴力做是O(n²)Ukkonen利用三条规则让每一轮扩展均摊O(1)规则1如果当前后缀已经存在不需要做任何操作直接沿用规则2如果需要在叶子后追加字符直接在叶子的边标签上延长一个字符规则3如果需要在内部节点处分裂就拆边、建节点、接后缀链接这三条规则配合后缀链接就是整棵后缀树的构建逻辑。看Handbook的图时建议把每个扩展步骤标上规则1/2/3你会发现自己对算法的理解瞬间清晰很多。3.4 构建复杂度为什么是O(n)均摊分析的直觉很多人看到Ukkonen算法会怀疑它真的O(n)吗每一轮不都要处理多个后缀吗关键在于每个字符只会导致有限次数的边分裂操作。虽然总共有O(n²)个后缀-前缀组合但真正需要在树上动手建节点、拆边的次数是O(n)的。叶子边标签可以用坐标(start, end)表示不需要真的拷贝字符串所以哪怕一个叶子边被延长了很多次实际的工作量也只是更新一下end坐标。这个均摊的思想跟并查集里的按秩合并有点像——看着好像每次操作很贵但全局算下来是线性的。4. 后缀数组与LCP用更小的常数拿到同样的能力后缀树很强但有一个工程上的痛点每个节点要存一堆指针内存占用大缓存不友好构建代码还复杂。后缀数组Suffix Array用一个单纯的一维数组就搞定了同样的信息。4.1 后缀数组的定义与构建方法后缀数组SA就是对S的所有后缀按字典序排序后记录每个后缀的起始下标。比如Sbanana$它的后缀和排序结果如下排序后下标顺序6($), 5(a$), 3(ana$), 1(anana$), 0(banana$), 4(na$), 2(nana$) SA [6, 5, 3, 1, 0, 4, 2]构建后缀数组的方法有三大流派朴素排序直接把n个后缀塞进排序算法。如果每次比较两个后缀需要O(n)时间总复杂度O(n² log n)只适合教学演示。倍增法Prefix DoublingO(n log n)最经典、最好写、最容易理解。思路是先按第一个字符排序再按前2个字符、前4个字符……因为每轮信息翻倍所以只需要log n轮。DC3 / SA-IS算法O(n)线性复杂度但实现复杂。工程库比如libdivsufsort里常用面试和手写一般不用。从Handbook的角度看它花了篇幅讲倍增法因为这是理解后缀数组与后缀树等价的桥梁。我个人建议首选学会倍增法它代码量不多逻辑清晰足够应付绝大多数场景。4.2 倍增法的核心步骤与代码骨架倍增法的核心思路可以描述成这样定义第k轮排名为每个后缀前2^k个字符的相对排名。第k1轮时每个后缀的排名可以用二元组(rank[i], rank[i2^k])来表示对这个二元组排序即可。下面这版代码是我自己常用的模板比较朴素但非常稳def build_sa(s): n len(s) sa list(range(n)) rank [ord(c) for c in s] tmp [0] * n k 1 while True: sa.sort(keylambda x: (rank[x], rank[x k] if x k n else -1)) tmp[sa[0]] 0 for i in range(1, n): prev, cur sa[i - 1], sa[i] prev_pair (rank[prev], rank[prev k] if prev k n else -1) cur_pair (rank[cur], rank[cur k] if cur k n else -1) tmp[cur] tmp[prev] (prev_pair ! cur_pair) rank, tmp tmp, rank if rank[sa[-1]] n - 1: break k 1 return sa这段代码虽然用了Python内置排序每轮O(n log n)的排序乘以log n轮整体O(n log² n)对大部分学习场景和中等规模数据处理完全够用。C里如果用std::sort配合基数排序优化可以压到O(n log n)。用这段模板跑一下banana$得到的SA就是[6, 5, 3, 1, 0, 4, 2]。建议你自己动手跑一遍把排序的二元组过程写出来比盯着书看十遍都管用。4.3 LCP数组后缀数组真正发力的地方后缀数组单独拿出来其实只是一个排序结果很多问题还得靠LCP数组才能解开。LCP数组通常记为lcp[i]表示SA中第i个后缀和第i1个后缀的最长公共前缀长度。为什么需要LCP因为排序相邻的两个后缀它们的公共前缀长度反映的是字符串中重复片段的信息。比如要找最长重复子串直接扫一遍LCP数组取最大值即可——这个子串就是排序后两个相邻后缀的公共前缀。看似简单但这是后缀数据结构最经典的应用之一。计算LCP数组有一个线性算法叫Kasai算法下面是非常简洁的版本def build_lcp(s, sa): n len(s) rank [0] * n for i, pos in enumerate(sa): rank[pos] i lcp [0] * (n - 1) h 0 for i in range(n): r rank[i] if r n - 1: h 0 continue j sa[r 1] while i h n and j h n and s[i h] s[j h]: h 1 lcp[r] h if h 0: h - 1 return lcp这段代码最关键的地方是那个h递减的优化跳过一个已经匹配的字符继续下一轮。基于的性质是如果第i个后缀参与匹配的LCP长度为h那么第i1个后缀参与匹配的LCP长度至少为h-1。这个性质让总比较次数均摊为O(n)所以Kasai算法是严格的O(n)。4.4 后缀树和后缀数组的等价性后缀数组和后缀树表面上差很多——一个是树一个是数组——但它们记录的信息是等价的。后缀树中每个内部节点对应一组拥有相同路径标签的后缀在后缀数组里这一组后缀是SA中连续的一个区间。反过来后缀数组配合LCP和RMQ区间最小值查询可以在O(1)时间内回答任意两个后缀的LCP长度这相当于模拟了后缀树的节点查询。所以我个人的使用经验是需要在线匹配、需要频繁动态扩展时后缀树方便需要离线处理、空间敏感的批处理任务后缀数组更香。Handbook这章的价值就在于它花了大量篇幅讲这两种表示如何互相转换读完你会觉得脑子里有一条翻译通道任何后缀树上能做的操作都能翻译成后缀数组LCP的操作反之亦然。5. 经典应用把后缀结构用起来数据结构学得再好不会用等于白学。这一节我把Handbook里提到的几个经典应用过一遍每个都给出具体解法思路和复杂度。5.1 子串搜索模式串是否出现过这是后缀结构最直观的应用。给定文本S预处理后缀树或后缀数组然后查询模式串P是否为S的子串。用后缀树做从根节点出发沿P的字符往下走如果能走完P说明P是某个后缀的前缀也就是S的子串。复杂度O(|P|)。用后缀数组做在SA上二分查找比较P与SA[mid]对应后缀复杂度O(|P| log n)。配合LCP可以优化到O(|P| log n)但一般二分就够。这个场景在全文搜索、代码检索、基因序列中找特定片段等场景都有应用。相比KMP每次查询O(n)的复杂度后缀结构预处理一次后每次查询只与模式串长度相关特别适合一次预处理、大量查询的场景。5.2 最长重复子串扫描LCP数组一个字符串中最长重复子串出现至少两次的子串怎么找用后缀数组的解法是构建SA和LCP数组答案就是LCP数组的最大值。因为任何重复子串都是某两个后缀的公共前缀而这两个后缀在字典序排序中相邻证明思路如果它们不相邻中间的后缀与它们的公共前缀会更长或相等可以通过调整使得相邻后缀对的LCP不小于它。这个题是我特别喜欢拿来练手的入门题因为代码量小但背后用到了后缀数组LCP两个核心结构非常适合检验自己有没有真正理解。5.3 最长公共子串两个字符串的公共片段给定两个字符串A和B求它们的最长公共子串。做法是把A和B通过一个分隔符#拼接成A#B#的字典序要在A和B所有字符之间构建新字符串的后缀数组和LCP数组。然后遍历LCP数组看i和i1这两个相邻后缀是否分别来自A和B。如果来自不同字符串且LCP值很大这个LCP值就是候选答案取最大值即可。这题背后的原理是A和B的任意公共子串一定是A#B中某两个分别来自A部分和B部分后缀的公共前缀。在排序后的SA中寻找最大LCP的相邻跨字符串后缀对就能找到最长公共子串。这个方法在生物信息学里特别常用比如两个基因组序列的保守区域分析。5.4 不同子串数量一个让初学者惊讶的结论还有一个很有趣的应用给定字符串S求它有多少个不同的子串。这个问题的答案可以这样算总不同子串数 n*(n1)/2 - sum(lcp[i])推倒思路是每个不同子串都对应某个后缀的某个前缀。不考虑去重时所有后缀前缀总数是n*(n1)/2。但很多前缀在不同后缀中重复出现重复的数量恰好可以用LCP数组减掉排序后每个后缀与前一个后缀的公共前缀长度就是该后缀贡献的已经被前面的后缀覆盖过的前缀数量。我第一次看到这个公式时觉得太漂亮了——一个看上去需要枚举所有子串去重的问题居然能用一个线性扫描的公式解决。5.5 后缀自动机、Burrows-Wheeler变换和后缀树的关系Handbook这一章还会提到一些更进阶的亲戚比如Burrows-Wheeler TransformBWT和后缀自动机SAM。BWT在数据压缩bzip2和生物信息学比对工具如Bowtie、BWA里是核心它的本质就是对SA中每个后缀取前一个字符构成的新串。理解了SABWT几乎不用额外学习就是把SA换一种表达方式。而后缀自动机则是一种更紧凑的自动机结构能够表示一个字符串的所有子串在有大量在线查询的场景中表现更好。如果你已经吃透了后缀树再去看SAM会感觉非常亲切因为两者的应用问题高度重合。6. 读Handbook这一章时最容易踩的坑下面这部分是我踩过的坑也是我在社区里看到很多人问过的问题集中说一下。6.1 把边标签实现成真正的字符串副本这是最经典的初学者错误。如果你在实现后缀树时每条边存一个独立的字符串那空间复杂度瞬间退化成O(n²)。对于长文本内存直接爆掉。正确做法是存(start, end)坐标对所有比较操作都从原字符串S中取字符。我在学的时候犯过这个错当时拿一个几十万字符的文档做测试内存占用直接到几个GB我还以为是后缀树本身内存大后来才反应过来是边标签实现的问题。改成坐标后内存占用降到了原来的几十分之一。6.2 后缀数组构建时忘了$终止符或分隔符后缀数组构建时如果原字符串本身没有终止符排序时会因为一个后缀是另一个后缀的前缀而产生歧义。所以构建SA之前要么在末尾加一个字典序最小的终止符要么在比较函数里单独特判边界。尤其在做两个字符串最长公共子串时中间的分隔符不能和字符串中原有字符相同而且要保证它的字典序在两边字符之间否则排序结果会错乱。我一般选#或者\0具体看字符集范围。6.3 把后缀树的O(n)构建当成必须手写这可能是很多人最大的心理障碍。Ukkonen算法确实精美但用手敲过你会发现边界条件极其容易出错一个小小的疏漏就可能导致活跃点计算错误整棵树就废了。我的建议是分阶段学习第一遍看懂Ukkonen的流程理解它为什么是O(n)会照着伪代码实现即可第二遍能独立手写并在LeetCode或OJ上跑通后缀数组相关题目实际工程中优先使用后缀数组Kasai算法因为代码量小、验证容易真需要在线后缀树的场景直接用现成库比如C的succinct库或Python的suffix_tree库6.4 忽略字典序细节导致排序错乱后缀数组的构建依赖稳定排序和字典序比较。如果字符集是ASCII还好说如果是Unicode或多字节编码不同语言的字符串比较规则可能会不一致导致排序结果与预期不同。在做工程时建议统一转成字节数组或整数序列再构建SA。7. 学习路线与三个可复现的练习最后聊一下怎么把这一章从看懂了变成真的会了。我自己的经验是只看书永远停留在感觉懂了的阶段必须配合写代码和刷题才能真正内化。Handbook给了很好的理论框架但动手实践要自己安排。7.1 练习一实现后缀数组和LCP数组这是最基本的一步。用Python或C实现倍增法构建SA再实现Kasai算法构建LCP然后用几个简单的字符串包括空串、单字符、全相同字符、随机串验证结果。一个验证方法是写一个朴素的SA生成函数直接对所有后缀排序和你的高效实现对比输出是否一致。随机生成几千个字符串做对拍测试能帮你发现大量隐藏bug。7.2 练习二用后缀数组解决三个经典问题快速刷这三个题它们能覆盖最核心的应用最长重复子串给定一个字符串输出任意一个最长重复子串两个字符串的最长公共子串不同子串的数量这三个题都不长但每一个都需要你去想我怎么从SA和LCP中提取答案而不是背公式。我建议先自己想10分钟想不出来再看题解收获会大很多。7.3 练习三读Handbook后面的进阶章节并做笔记Handbook这一章的结尾一般会提到后缀树变体和扩展应用比如更节省空间的压缩后缀数组、面向DNA序列的二元后缀树等。这些内容可以作为延伸阅读。每读一个变体都回到基础问题问自己它优化了什么代价是什么——这个问题能帮你把知识串成网而不是记一堆孤立的算法名称。8. 一些关于学习节奏的实在建议如果你准备用两周时间拿下这一章我建议这样分配第一周建立直觉读懂Handbook的定义部分画后缀树、后缀数组的手工构建过程实现一次朴素版后缀数组能跑通即可。第二周深入算法学Ukkonen和倍增法刷上面三道经典题最后再看一遍LCP和应用章节。如果时间更紧我个人的优先级是后缀数组LCP 后缀树应用 Ukkonen细节。原因很简单工程中用后缀数组的场景更多而且只要理解了后缀数组和后缀树的等价性遇到真正需要后缀树的场景你也能很快切换过去。这个内容后续还可以这样扩展如果对生物信息学感兴趣可以继续研究BWT和FM-index它们是基于后缀数组的衍生结构在DNA序列比对中应用极广如果对算法竞赛感兴趣可以挑战更多的后缀数据结构硬核题。但不管走哪个方向Handbook这一章打下的底子都不会白费。
手头这本《Handbook of Data Structures and Applications》我翻得最多、折角最多的一章就是关于Suffix Trees和Suffix Arrays的部分。别看后缀树Suffix Trees和后缀数组Suffix Arrays这俩名字听起来像某个竞赛选手的私藏套路实际上它们是字符串处理领域里最能打的一套底层结构基因组序列比对、全文检索、数据压缩、自然语言处理里的最长公共子串背后全是它们在撑场面。这篇就把我啃这一章时的完整笔记、推导过程和踩坑经验整理出来适合正在学Data Structures进阶内容、准备面试算法题、或者做文本处理相关项目的朋友参考。1. 为什么后缀结构是字符串算法里的万能钥匙先聊个比较反直觉的事实很多看起来毫无关联的字符串问题比如一个字符串里出现次数最多的重复片段是什么两个超长DNA序列的公共部分有多长一段文本里有没有出现过某个模式串本质上都能归约成同一个操作——高效比较一堆字符串后缀之间的公共前缀。后缀树和后缀数组这两个数据结构就是为这个操作量身定做的。1.1 从朴素方法到后缀结构的思维跳跃假设你手里有一个长度为n的字符串S想找出它的最长重复子串。最笨的办法是枚举所有子串两两比较复杂度O(n³)甚至更高。稍微聪明一点的做法是枚举所有后缀因为任何一个子串都是某个后缀的前缀所以找重复子串等价于找两个后缀的最长公共前缀。但问题是一个长度为n的字符串有n个后缀两两比较还是O(n²)级别。对于人类基因组这种长度在30亿级别的输入这个复杂度等于没有算法。后缀树的核心思路就是把n个后缀一次性压进一棵树里让每次公共前缀比较的耗时从O(n)级别降下来。我第一次看到这个想法时觉得特别惊艳——它本质上是在用空间换时间把查询时反复比较字符串的代价转化为构建时一次性预处理的代价。1.2 Handbook这一章在整本书里的定位《Handbook of Data Structures and Applications》是一本非常工业级的参考书它不是ACM竞赛教材那种上来就丢定理的风格而是每个数据结构都讲清楚动机-定义-构建-应用-变种。后缀树和后缀数组这一章继承了这个特点前半部分用大量图例讲清楚后缀树到底长什么样后半部分花了不少篇幅讲后缀数组与LCPLongest Common Prefix最长公共前缀数组之间的关系。如果你和我一样是自学我强烈建议不要把这一章当小说一样从头读到尾而是先看目录搞清楚它把内容拆成了哪几块。Handbook这一章的逻辑大致是这样后缀树的定义与基本性质Ukkonen在线构建算法或者至少讲清楚为什么朴素构建不行后缀数组的定义与构建方法LCP数组及其在问题求解中的作用后缀树与后缀数组的等价转换实际应用案例我读下来的体会是这章的前三节是重中之重后面的内容基本都是在反复使用前三节建立起来的核心概念。1.3 这一章适合谁读、读之前需要什么基础如果你想把这一章真正啃下来我建议先具备三样东西熟悉Trie前缀树的插入与查询逻辑因为后缀树本质是一棵压缩过的后缀Trie理解分治法和倍增法的基本思想因为后缀数组的构建算法大量用到这些思路有一点耐心去推演边界条件比如处理空串、单字符、所有字符相同等特殊情况如果这三样都还没有建议先回去补补基础再来看这一章。不然很容易被Ukkonen算法那套活跃点剩余数的概念劝退。2. 后缀树到底是什么从Trie到压缩树的进化后缀树定义看起来很简单包含字符串S所有后缀的一棵压缩Trie。但这个定义里两个词都暗藏玄机——所有后缀和压缩。2.1 后缀是什么、为什么必须用终止符字符串S banana的后缀集合是bananaananananaananaa如果把这6个后缀直接插入一棵普通Trie你会得到一个后缀Trie。问题来了有些后缀是另一些后缀的前缀比如a是ana的前缀这样从根节点走到叶子节点的路径可能对应多个后缀树的叶子节点和后缀的对应关系就乱了。解决办法是在字符串末尾加一个字典序最小的唯一终止符比如$让每个后缀都以一个永不在字符串内部出现的字符结尾。于是S变成banana$后缀变成banana$anana$nana$ana$na$a$$——现在没有任何后缀是另一个后缀的前缀了每个后缀都恰好对应一条从根到叶子的路径。这个终止符看着不起眼但它解决了一个非常关键的问题确保每个后缀能被唯一地标识为一条根到叶子的路径。2.2 压缩Trie为什么必须把链压成边不加压缩的后缀Trie有一个致命问题插入n个后缀总节点数可以达到O(n²)。还是拿banana举例所有后缀共享了大量前缀但如果是abcdefg...这种没有公共前缀的字符串普通Trie里就会出现很多只有一个孩子的中间节点——它们只承担了传递的功能没有提供任何分叉信息。压缩Trie的做法很直接把只有一个孩子的节点直接合并到边上边上存的不再是单个字符而是一个子串。这样一棵树里每个内部节点都至少有2个孩子叶子节点的数量等于后缀数量n因此内部节点数不超过n-1整棵树的节点总数变成O(n)。这就是后缀树比后缀Trie强大的根本原因信息量一点没少但空间从O(n²)降到了O(n)。这种把链条压成边的思路在芬威克树、线段树的离散化等很多数据结构里都有类似的影子但后缀树是把它用到极致的地方。2.3 后缀树上怎么挂数据边标签与路径标签后缀树的每条边都携带一个子串标签从根节点到某个内部节点或叶子的路径上所有边标签拼接起来就是路径标签。如果这个路径标签恰好是S的某个后缀的前缀那么这个节点就对应字符串中的一个位置。Handbook里有几个非常容易混的概念我一开始看的时候被绕了好久边标签edge label边上存的子串在S中的起止位置路径标签path label从根到某节点的路径上所有边标签的拼接叶子节点对应一个唯一后缀内部节点对应一组后缀的公共前缀实现时一般不会真的在每条边上存一个字符串副本而是存两个整数坐标(start, end)指向S中的某个闭区间。这个优化非常关键它让后缀树的存储空间真正做到了O(n)而不是O(n²)。后面写代码实现时一定要记住这一点否则存字符串副本能把你内存打爆。2.4 后缀树的几个重要性质性质这东西光背结论没用最好能自己推一遍。我发现只要抓住下面三点后面看应用的时候就顺多了叶子节点数 n因为每个后缀对应一个叶子这是定义保证的。内部节点数 ≤ n-1每个内部节点至少2个孩子整棵树是满的full压缩树所以节点总数不超过2n-1。每个内部节点的路径标签都是S中出现过至少2次的子串这是公共前缀的直接推论也是用后缀树找重复子串的理论基础。这三条性质撑起了后缀树几乎所有应用场景。最长重复子串、最长公共子串、模式匹配全都是在这三条性质上做文章。3. Ukkonen构建算法在线构建后缀树的硬核之处后缀树的朴素构建法非常直观从S的第一个字符开始不断把新的后缀插入到树里。但这样做的总复杂度是O(n²)因为每次插入都可能要重新从根节点走一遍。对于n很大的情况这不能接受。Ukkonen算法把这个过程优化到了O(n)——而且它是在线的也就是从左到右扫描一遍S每读入一个字符就更新出当前前缀的后缀树。3.1 为什么朴素插入是O(n²)的假设已经建好了S[1..i]的后缀树现在要插入第i1个字符让树变成S[1..i1]的后缀树。从根开始需要找到新后缀应该挂在哪个位置。如果从根重新走一遍每次匹配一个字符都要比较平均要走O(n)步。i从1到n总复杂度O(n²)。这个复杂度对banana这种短字符串无所谓但对实际应用中几百万甚至上亿字符的文本完全不可行。所以Ukkonen才是后缀树构建里的主角。3.2 Ukkonen的核心思想后缀链接与活跃点Ukkonen算法引入了一堆让人头大的术语活跃点active point、剩余数remainder、后缀链接suffix link。我第一次看的时候满脑子都是这到底在干嘛。后来我找到了一种比较生活化的理解方式。想象你在一家甜品店排队队伍里的每个人代表一个需要被更新的后缀。每读入一个新字符队伍里所有人都要往前挪一步新后缀出现所有旧后缀都变长了。但你不必一次性处理所有人——Ukkonen算法的妙处就在于懒惰更新。它维护一个活跃三元组(active_node, active_edge, active_length)表示当前最新需要处理的后缀离正确位置还差多少步然后用剩余数remainder记录还有多少个后缀待插入。每次处理新字符时只需要从活跃点出发沿着活跃边往下走能走就走走不动了就拆边、建内部节点、连后缀链接。后缀链接相当于是树里的快捷方式它让从一条路径跳转到另一条路径变成O(1)操作而不是重新从根匹配。如果你觉得这些概念太抽象我的建议是先放下我一定要马上学会手写Ukkonen这个执念。很多教科书把这章列为核心是因为它是理论上的巅峰但实际工程中用后缀数组的倍增法或DC3算法更常见构建代码也更好写。理解Ukkonen的为什么在线为什么O(n)即可不一定要做到能默写。3.3 Handbook对Ukkonen的讲解特点Handbook这一章有个很贴心的设计它先讲了后缀树的定义和朴素构建然后才进入Ukkonen而且给出了不少图示。我不否认这本书的图示密度不如专题性论文但它好就好在把Ukkonen算法拆成了延伸extension这个原子操作。Ukkonen算法本质上做了n轮扩展第i轮读完S[i]之后对j从1到i把后缀S[j..i]加入树中。但暴力做是O(n²)Ukkonen利用三条规则让每一轮扩展均摊O(1)规则1如果当前后缀已经存在不需要做任何操作直接沿用规则2如果需要在叶子后追加字符直接在叶子的边标签上延长一个字符规则3如果需要在内部节点处分裂就拆边、建节点、接后缀链接这三条规则配合后缀链接就是整棵后缀树的构建逻辑。看Handbook的图时建议把每个扩展步骤标上规则1/2/3你会发现自己对算法的理解瞬间清晰很多。3.4 构建复杂度为什么是O(n)均摊分析的直觉很多人看到Ukkonen算法会怀疑它真的O(n)吗每一轮不都要处理多个后缀吗关键在于每个字符只会导致有限次数的边分裂操作。虽然总共有O(n²)个后缀-前缀组合但真正需要在树上动手建节点、拆边的次数是O(n)的。叶子边标签可以用坐标(start, end)表示不需要真的拷贝字符串所以哪怕一个叶子边被延长了很多次实际的工作量也只是更新一下end坐标。这个均摊的思想跟并查集里的按秩合并有点像——看着好像每次操作很贵但全局算下来是线性的。4. 后缀数组与LCP用更小的常数拿到同样的能力后缀树很强但有一个工程上的痛点每个节点要存一堆指针内存占用大缓存不友好构建代码还复杂。后缀数组Suffix Array用一个单纯的一维数组就搞定了同样的信息。4.1 后缀数组的定义与构建方法后缀数组SA就是对S的所有后缀按字典序排序后记录每个后缀的起始下标。比如Sbanana$它的后缀和排序结果如下排序后下标顺序6($), 5(a$), 3(ana$), 1(anana$), 0(banana$), 4(na$), 2(nana$) SA [6, 5, 3, 1, 0, 4, 2]构建后缀数组的方法有三大流派朴素排序直接把n个后缀塞进排序算法。如果每次比较两个后缀需要O(n)时间总复杂度O(n² log n)只适合教学演示。倍增法Prefix DoublingO(n log n)最经典、最好写、最容易理解。思路是先按第一个字符排序再按前2个字符、前4个字符……因为每轮信息翻倍所以只需要log n轮。DC3 / SA-IS算法O(n)线性复杂度但实现复杂。工程库比如libdivsufsort里常用面试和手写一般不用。从Handbook的角度看它花了篇幅讲倍增法因为这是理解后缀数组与后缀树等价的桥梁。我个人建议首选学会倍增法它代码量不多逻辑清晰足够应付绝大多数场景。4.2 倍增法的核心步骤与代码骨架倍增法的核心思路可以描述成这样定义第k轮排名为每个后缀前2^k个字符的相对排名。第k1轮时每个后缀的排名可以用二元组(rank[i], rank[i2^k])来表示对这个二元组排序即可。下面这版代码是我自己常用的模板比较朴素但非常稳def build_sa(s): n len(s) sa list(range(n)) rank [ord(c) for c in s] tmp [0] * n k 1 while True: sa.sort(keylambda x: (rank[x], rank[x k] if x k n else -1)) tmp[sa[0]] 0 for i in range(1, n): prev, cur sa[i - 1], sa[i] prev_pair (rank[prev], rank[prev k] if prev k n else -1) cur_pair (rank[cur], rank[cur k] if cur k n else -1) tmp[cur] tmp[prev] (prev_pair ! cur_pair) rank, tmp tmp, rank if rank[sa[-1]] n - 1: break k 1 return sa这段代码虽然用了Python内置排序每轮O(n log n)的排序乘以log n轮整体O(n log² n)对大部分学习场景和中等规模数据处理完全够用。C里如果用std::sort配合基数排序优化可以压到O(n log n)。用这段模板跑一下banana$得到的SA就是[6, 5, 3, 1, 0, 4, 2]。建议你自己动手跑一遍把排序的二元组过程写出来比盯着书看十遍都管用。4.3 LCP数组后缀数组真正发力的地方后缀数组单独拿出来其实只是一个排序结果很多问题还得靠LCP数组才能解开。LCP数组通常记为lcp[i]表示SA中第i个后缀和第i1个后缀的最长公共前缀长度。为什么需要LCP因为排序相邻的两个后缀它们的公共前缀长度反映的是字符串中重复片段的信息。比如要找最长重复子串直接扫一遍LCP数组取最大值即可——这个子串就是排序后两个相邻后缀的公共前缀。看似简单但这是后缀数据结构最经典的应用之一。计算LCP数组有一个线性算法叫Kasai算法下面是非常简洁的版本def build_lcp(s, sa): n len(s) rank [0] * n for i, pos in enumerate(sa): rank[pos] i lcp [0] * (n - 1) h 0 for i in range(n): r rank[i] if r n - 1: h 0 continue j sa[r 1] while i h n and j h n and s[i h] s[j h]: h 1 lcp[r] h if h 0: h - 1 return lcp这段代码最关键的地方是那个h递减的优化跳过一个已经匹配的字符继续下一轮。基于的性质是如果第i个后缀参与匹配的LCP长度为h那么第i1个后缀参与匹配的LCP长度至少为h-1。这个性质让总比较次数均摊为O(n)所以Kasai算法是严格的O(n)。4.4 后缀树和后缀数组的等价性后缀数组和后缀树表面上差很多——一个是树一个是数组——但它们记录的信息是等价的。后缀树中每个内部节点对应一组拥有相同路径标签的后缀在后缀数组里这一组后缀是SA中连续的一个区间。反过来后缀数组配合LCP和RMQ区间最小值查询可以在O(1)时间内回答任意两个后缀的LCP长度这相当于模拟了后缀树的节点查询。所以我个人的使用经验是需要在线匹配、需要频繁动态扩展时后缀树方便需要离线处理、空间敏感的批处理任务后缀数组更香。Handbook这章的价值就在于它花了大量篇幅讲这两种表示如何互相转换读完你会觉得脑子里有一条翻译通道任何后缀树上能做的操作都能翻译成后缀数组LCP的操作反之亦然。5. 经典应用把后缀结构用起来数据结构学得再好不会用等于白学。这一节我把Handbook里提到的几个经典应用过一遍每个都给出具体解法思路和复杂度。5.1 子串搜索模式串是否出现过这是后缀结构最直观的应用。给定文本S预处理后缀树或后缀数组然后查询模式串P是否为S的子串。用后缀树做从根节点出发沿P的字符往下走如果能走完P说明P是某个后缀的前缀也就是S的子串。复杂度O(|P|)。用后缀数组做在SA上二分查找比较P与SA[mid]对应后缀复杂度O(|P| log n)。配合LCP可以优化到O(|P| log n)但一般二分就够。这个场景在全文搜索、代码检索、基因序列中找特定片段等场景都有应用。相比KMP每次查询O(n)的复杂度后缀结构预处理一次后每次查询只与模式串长度相关特别适合一次预处理、大量查询的场景。5.2 最长重复子串扫描LCP数组一个字符串中最长重复子串出现至少两次的子串怎么找用后缀数组的解法是构建SA和LCP数组答案就是LCP数组的最大值。因为任何重复子串都是某两个后缀的公共前缀而这两个后缀在字典序排序中相邻证明思路如果它们不相邻中间的后缀与它们的公共前缀会更长或相等可以通过调整使得相邻后缀对的LCP不小于它。这个题是我特别喜欢拿来练手的入门题因为代码量小但背后用到了后缀数组LCP两个核心结构非常适合检验自己有没有真正理解。5.3 最长公共子串两个字符串的公共片段给定两个字符串A和B求它们的最长公共子串。做法是把A和B通过一个分隔符#拼接成A#B#的字典序要在A和B所有字符之间构建新字符串的后缀数组和LCP数组。然后遍历LCP数组看i和i1这两个相邻后缀是否分别来自A和B。如果来自不同字符串且LCP值很大这个LCP值就是候选答案取最大值即可。这题背后的原理是A和B的任意公共子串一定是A#B中某两个分别来自A部分和B部分后缀的公共前缀。在排序后的SA中寻找最大LCP的相邻跨字符串后缀对就能找到最长公共子串。这个方法在生物信息学里特别常用比如两个基因组序列的保守区域分析。5.4 不同子串数量一个让初学者惊讶的结论还有一个很有趣的应用给定字符串S求它有多少个不同的子串。这个问题的答案可以这样算总不同子串数 n*(n1)/2 - sum(lcp[i])推倒思路是每个不同子串都对应某个后缀的某个前缀。不考虑去重时所有后缀前缀总数是n*(n1)/2。但很多前缀在不同后缀中重复出现重复的数量恰好可以用LCP数组减掉排序后每个后缀与前一个后缀的公共前缀长度就是该后缀贡献的已经被前面的后缀覆盖过的前缀数量。我第一次看到这个公式时觉得太漂亮了——一个看上去需要枚举所有子串去重的问题居然能用一个线性扫描的公式解决。5.5 后缀自动机、Burrows-Wheeler变换和后缀树的关系Handbook这一章还会提到一些更进阶的亲戚比如Burrows-Wheeler TransformBWT和后缀自动机SAM。BWT在数据压缩bzip2和生物信息学比对工具如Bowtie、BWA里是核心它的本质就是对SA中每个后缀取前一个字符构成的新串。理解了SABWT几乎不用额外学习就是把SA换一种表达方式。而后缀自动机则是一种更紧凑的自动机结构能够表示一个字符串的所有子串在有大量在线查询的场景中表现更好。如果你已经吃透了后缀树再去看SAM会感觉非常亲切因为两者的应用问题高度重合。6. 读Handbook这一章时最容易踩的坑下面这部分是我踩过的坑也是我在社区里看到很多人问过的问题集中说一下。6.1 把边标签实现成真正的字符串副本这是最经典的初学者错误。如果你在实现后缀树时每条边存一个独立的字符串那空间复杂度瞬间退化成O(n²)。对于长文本内存直接爆掉。正确做法是存(start, end)坐标对所有比较操作都从原字符串S中取字符。我在学的时候犯过这个错当时拿一个几十万字符的文档做测试内存占用直接到几个GB我还以为是后缀树本身内存大后来才反应过来是边标签实现的问题。改成坐标后内存占用降到了原来的几十分之一。6.2 后缀数组构建时忘了$终止符或分隔符后缀数组构建时如果原字符串本身没有终止符排序时会因为一个后缀是另一个后缀的前缀而产生歧义。所以构建SA之前要么在末尾加一个字典序最小的终止符要么在比较函数里单独特判边界。尤其在做两个字符串最长公共子串时中间的分隔符不能和字符串中原有字符相同而且要保证它的字典序在两边字符之间否则排序结果会错乱。我一般选#或者\0具体看字符集范围。6.3 把后缀树的O(n)构建当成必须手写这可能是很多人最大的心理障碍。Ukkonen算法确实精美但用手敲过你会发现边界条件极其容易出错一个小小的疏漏就可能导致活跃点计算错误整棵树就废了。我的建议是分阶段学习第一遍看懂Ukkonen的流程理解它为什么是O(n)会照着伪代码实现即可第二遍能独立手写并在LeetCode或OJ上跑通后缀数组相关题目实际工程中优先使用后缀数组Kasai算法因为代码量小、验证容易真需要在线后缀树的场景直接用现成库比如C的succinct库或Python的suffix_tree库6.4 忽略字典序细节导致排序错乱后缀数组的构建依赖稳定排序和字典序比较。如果字符集是ASCII还好说如果是Unicode或多字节编码不同语言的字符串比较规则可能会不一致导致排序结果与预期不同。在做工程时建议统一转成字节数组或整数序列再构建SA。7. 学习路线与三个可复现的练习最后聊一下怎么把这一章从看懂了变成真的会了。我自己的经验是只看书永远停留在感觉懂了的阶段必须配合写代码和刷题才能真正内化。Handbook给了很好的理论框架但动手实践要自己安排。7.1 练习一实现后缀数组和LCP数组这是最基本的一步。用Python或C实现倍增法构建SA再实现Kasai算法构建LCP然后用几个简单的字符串包括空串、单字符、全相同字符、随机串验证结果。一个验证方法是写一个朴素的SA生成函数直接对所有后缀排序和你的高效实现对比输出是否一致。随机生成几千个字符串做对拍测试能帮你发现大量隐藏bug。7.2 练习二用后缀数组解决三个经典问题快速刷这三个题它们能覆盖最核心的应用最长重复子串给定一个字符串输出任意一个最长重复子串两个字符串的最长公共子串不同子串的数量这三个题都不长但每一个都需要你去想我怎么从SA和LCP中提取答案而不是背公式。我建议先自己想10分钟想不出来再看题解收获会大很多。7.3 练习三读Handbook后面的进阶章节并做笔记Handbook这一章的结尾一般会提到后缀树变体和扩展应用比如更节省空间的压缩后缀数组、面向DNA序列的二元后缀树等。这些内容可以作为延伸阅读。每读一个变体都回到基础问题问自己它优化了什么代价是什么——这个问题能帮你把知识串成网而不是记一堆孤立的算法名称。8. 一些关于学习节奏的实在建议如果你准备用两周时间拿下这一章我建议这样分配第一周建立直觉读懂Handbook的定义部分画后缀树、后缀数组的手工构建过程实现一次朴素版后缀数组能跑通即可。第二周深入算法学Ukkonen和倍增法刷上面三道经典题最后再看一遍LCP和应用章节。如果时间更紧我个人的优先级是后缀数组LCP 后缀树应用 Ukkonen细节。原因很简单工程中用后缀数组的场景更多而且只要理解了后缀数组和后缀树的等价性遇到真正需要后缀树的场景你也能很快切换过去。这个内容后续还可以这样扩展如果对生物信息学感兴趣可以继续研究BWT和FM-index它们是基于后缀数组的衍生结构在DNA序列比对中应用极广如果对算法竞赛感兴趣可以挑战更多的后缀数据结构硬核题。但不管走哪个方向Handbook这一章打下的底子都不会白费。
