手头这本《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竞赛教材那种上来就丢定理的风格，而是每个数据结构都讲清楚"动机-定义-构建-应用-变种"。后缀树和后缀数组这一章继承了这个特点：前半部分用大量图例讲清楚后缀树到底长什么样，后半部分花了不少篇幅讲后缀数组与LCP（Longest Common Prefix，最长公共前缀）数组之间的关系。
如果你和我一样是自学，我强烈建议不要把这一章当小说一样从头读到尾，而是先看目录，搞清楚它把内容拆成了哪几块。Handbook这一章的逻辑大致是这样：
- 后缀树的定义与基本性质
- Ukkonen在线构建算法（或者至少讲清楚为什么朴素构建不行）
- 后缀数组的定义与构建方法
- LCP数组及其在问题求解中的作用
- 后缀树与后缀数组的等价转换
- 实际应用案例
我读下来的体会是：这章的前三节是重中之重，后面的内容基本都是在反复使用前三节建立起来的核心概念。
1.3 这一章适合谁读、读之前需要什么基础
如果你想把这一章真正啃下来，我建议先具备三样东西：
- 熟悉Trie（前缀树）的插入与查询逻辑，因为后缀树本质是一棵压缩过的后缀Trie
- 理解分治法和倍增法的基本思想，因为后缀数组的构建算法大量用到这些思路
- 有一点耐心去推演边界条件，比如处理空串、单字符、所有字符相同等特殊情况
如果这三样都还没有，建议先回去补补基础再来看这一章。不然很容易被Ukkonen算法那套"活跃点""剩余数"的概念劝退。
2. 后缀树到底是什么：从Trie到压缩树的进化
后缀树定义看起来很简单：包含字符串S所有后缀的一棵压缩Trie。但这个定义里两个词都暗藏玄机——"所有后缀"和"压缩"。
2.1 后缀是什么、为什么必须用终止符
字符串S = "banana"的后缀集合是：
- banana
- anana
- nana
- ana
- na
- a
如果把这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]的后缀树，现在要插入第i+1个字符，让树变成S[1..i+1]的后缀树。从根开始，需要找到"新后缀应该挂在哪个位置"。如果从根重新走一遍，每次匹配一个字符都要比较，平均要走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的所有后缀按字典序排序后，记录每个后缀的起始下标。比如S="banana$"，它的后缀和排序结果如下：
排序后下标顺序：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 Doubling）：O(n log n)，最经典、最好写、最容易理解。思路是先按第一个字符排序，再按前2个字符、前4个字符……因为每轮信息翻倍，所以只需要log n轮。
- DC3 / SA-IS算法：O(n)线性复杂度，但实现复杂。工程库（比如libdivsufsort）里常用，面试和手写一般不用。
从Handbook的角度看，它花了篇幅讲倍增法，因为这是理解后缀数组"与后缀树等价"的桥梁。我个人建议：首选学会倍增法，它代码量不多，逻辑清晰，足够应付绝大多数场景。
4.2 倍增法的核心步骤与代码骨架
倍增法的核心思路可以描述成这样：定义"第k轮排名"为每个后缀前2^k个字符的相对排名。第k+1轮时，每个后缀的排名可以用二元组(rank[i], rank[i+2^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(key=lambda 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个后缀和第i+1个后缀的最长公共前缀长度。
为什么需要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，那么第i+1个后缀参与匹配的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和i+1这两个相邻后缀是否分别来自A和B。如果来自不同字符串，且LCP值很大，这个LCP值就是候选答案，取最大值即可。
这题背后的原理是：A和B的任意公共子串，一定是A#B中某两个分别来自A部分和B部分后缀的公共前缀。在排序后的SA中，寻找最大LCP的相邻跨字符串后缀对，就能找到最长公共子串。
这个方法在生物信息学里特别常用，比如两个基因组序列的保守区域分析。
5.4 不同子串数量：一个让初学者惊讶的结论
还有一个很有趣的应用：给定字符串S，求它有多少个不同的子串。
这个问题的答案可以这样算：
总不同子串数 = n*(n+1)/2 - sum(lcp[i])推倒思路是：每个不同子串都对应"某个后缀的某个前缀"。不考虑去重时，所有后缀前缀总数是n*(n+1)/2。但很多前缀在不同后缀中重复出现，重复的数量恰好可以用LCP数组减掉：排序后，每个后缀与前一个后缀的公共前缀长度，就是该后缀贡献的"已经被前面的后缀覆盖过"的前缀数量。
我第一次看到这个公式时觉得太漂亮了——一个看上去需要枚举所有子串去重的问题，居然能用一个线性扫描的公式解决。
5.5 后缀自动机、Burrows-Wheeler变换和后缀树的关系
Handbook这一章还会提到一些更进阶的"亲戚"，比如Burrows-Wheeler Transform（BWT）和后缀自动机（SAM）。BWT在数据压缩（bzip2）和生物信息学比对工具（如Bowtie、BWA）里是核心，它的本质就是对SA中每个后缀取前一个字符构成的新串。理解了SA，BWT几乎不用额外学习，就是把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这一章打下的底子都不会白费。
