17篇固定模式、扫描文本。若文本固定而查询模式不断变化，每次重新扫描长度n的文本会重复付出O(n)成本。后缀数组把文本的全部非空后缀排序，使同一模式的所有出现位置对应一个连续区间。

文本banana的后缀数组是[5,3,1,0,4,2]，依次对应a, ana, anana, banana, na, nana。查询ana得到数组中的连续两项[3,1]。结果按后缀字典序排列，不自动按文本起点递增。

固定文本的查询契约

沿用17篇Unicode码点和精确字符相等语义，不做归一化。文本长度n，查询模式长度m，命中数z。索引包含n个非空后缀；空文本的后缀数组为空。模式必须非空，否则抛出ValueError。

SuffixIndex(text).find(pattern)返回后缀数组顺序的匹配起点，保留重叠。固定文本不能原地更新：改变一个字符可能改变许多后缀的顺序，当前接口要求重新建立索引。若需要按文本位置排序，另计O(z log(z+1))时间。

后缀数组SA是起点0到n−1的一个排列，满足T[SA[r]:]按字典序递增。实现不存这些完整切片；切片只在独立的小规模参照中使用。长度为n的文本若物化全部后缀，总字符数是n(n+1)/2，不能仍声称线性存储。

倍增把字符串比较转成排名比较

先用字符码点值表示单字符排名；这里只需要相对次序正确，相等字符取相同值，不要求初始排名连续。假设当前rank[i]正确表示从i开始、长度至多q的文本前缀的相对次序。长度至多2q的前缀由两段组成，所以可用二元组表示：

(rank[i], rank[i+q])(rank[i],\ rank[i+q])

越过文本末尾的第二项使用−1；有效排名均非负，使结束位置在共同前缀之后先于任何继续的字符。按二元组排序，扫描相邻元组，相同者赋相同新排名，不同者递增。随后q翻倍。

正确性来自字典序的分段性质：第一段不同，整个前缀的次序已确定；第一段相同，比较第二段即可。由q=1的字符排名归纳，覆盖整个文本后排名就是后缀排名。若中途已有n个不同排名，也能提前结束，因为当前前缀已经区分所有后缀。

教学实现每轮用Python比较排序排列排名二元组。单位成本整数比较模型下，一轮最坏O(n log(n+1))，至多O(log(n+1))轮，因此构建最坏O(n log²(n+1))，额外空间O(n)。这不是采用线性整数排序的倍增版本，更不是线性后缀数组算法。

若改用两趟稳定计数排序，且排名范围保持O(n)，每轮可以O(n)，总计O(n log n)。这里“稳定”不能省略：先按第二关键字排序，再按第一关键字稳定排序，才保留相同第一关键字内部的第二关键字次序。不同实现的界不能交换使用。

相邻LCP为什么能线性建立

定义LCP[0]=0，其余LCP[r]为SA[r−1]和SA[r]两个后缀的最长公共前缀长度。banana对应[0,1,3,0,0,2]。先由SA建立逆排名pos，使pos[SA[r]]=r。

Kasai算法按文本起点i递增处理，而不是按SA顺序处理。若上一步公共前缀长度为h，去掉双方首字符后，仍能复用至少max(h−1,0)个相等字符。相邻次序的性质保证，当前后缀与它的真正字典序前驱的公共前缀不短于这个可复用下界；从该下界继续比较即可。

一种说明是：此前的两个后缀去掉相同首字符后，次序保持，且共享h−1长度前缀。任何位于它们之间的后缀也共享这段前缀，因此当前后缀的直接前驱不会破坏下界。边界h=0时只提供零下界。

循环中h每次最多减1，成功字符比较才增加h，且h不超过n。因此累计成功比较O(n)，每个起点另有常数次终止检查，总时间最坏O(n)。逆排名和LCP数组占O(n)空间。该结论以SA已正确构建为前提，不包含上节的排序成本。

当前起点排名为0时没有前驱，必须把h设为0并跳过。Python中直接使用SA[−1]不会报错，而会取最后一项，可能悄悄制造错误LCP。实现不附加结束哨兵，所有字符比较都显式检查文本边界；不能把原论文带唯一结束标记的代码原样删去标记后运行。

两次边界搜索定位全部命中

给定模式P，比较一个后缀与P时逐字符前进：首个不同字符决定小于或大于；模式耗尽表示它是该后缀的前缀，记为相等；后缀先耗尽则小于模式。

按这个比较结果，SA上先出现“小于”，再是“相等”，最后是“大于”。一次二分寻找首个不小于的位置，另一次寻找首个大于的位置，两者之间就是全部命中。相等段连续，因为字典序中夹在两个共同前缀字符串之间的字符串也必须共享此前缀。

每次比较至多读m个字符，两次二分各O(log(n+1))次，因此单次查询最坏O(m log(n+1)+z)。空文本直接返回空表。很多后缀共享长前缀时，各次比较仍可能反复读取模式；仅仅建立LCP数组不会自动把这个查询实现变成O(m+log n+z)。要达到更强的界，必须另外实现并证明利用LCP信息的搜索过程。

RMQ连接任意两条后缀

对两个不同起点i、j，设a=min(pos[i],pos[j])、b=max(pos[i],pos[j])，则

lcp⁡(T[i:],T[j:])=min⁡a<r≤bLCP[r].\operatorname{lcp}(T[i:],T[j:])=\min_{a<r\le b}LCP[r].

所有相邻对都共享长度至少d，沿排序区间传递可知两端也共享d；反过来，两端共享的前缀也属于区间中每条后缀，所以中间的相邻LCP不会更小。两方向合在一起得到等式。i=j时直接返回n−i，无须查询空区间。

接到13篇已有的半开RMQ接口时，区间是[a+1,b+1)。SparseMin.argmin返回数组下标，因此还要用该下标读取LCP值，不能把下标当作公共前缀长度。稀疏表需O(n log(n+1))预处理与空间，之后每次RMQ最坏O(1)。这会改变整个索引的空间成本。

本篇教学程序实现并验证SA、LCP和朴素二分查询；RMQ连接在此给出数学与接口推导。第13篇运行检查受当前环境限制，相关集成没有执行，也没有借本篇的通过记录将其改标为已验证。

可复跑检查

实现位于examples/advanced-algorithms/suffix_index.py。辅助接口kasai_lcp(text, sa)检查长度与排列合法性，但不重新检查字典序；调用者须传入正确SA，正常由suffix_array生成。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_suffix_index.py

独立参照在短文本上物化后缀后排序，相邻LCP直接逐字符比较；模式查询用startswith筛选参照SA。实际运行枚举511个长度0到8的二元文本，通过15330次查询；另有5个边界文本、17次查询与6次拒绝检查，覆盖重复字符、Unicode、空文本、零字符和非法排列。真实输出保存于examples/advanced-algorithms/results/suffix_index.json。

有限检查用于发现排名更新、越界与二分边界错误，不能替代上述归纳和总成本证明。检查没有导入或运行第13篇代码；也未测量大文本索引延迟、进程内存或Unicode归一化行为。

练习

  1. 手算aaaa的SA和LCP，列出查询aa的结果顺序。若把越界第二排名设成最大值，哪两条后缀的顺序首先可能出错？
  2. 对banana的起点1和3，写出逆排名、RMQ半开区间及答案。再解释i=j时为什么必须单独处理，不能查询长度为0的RMQ区间。

参考资料