后缀数组
后缀数组按字典序存储每个后缀的起始位置。文本固定、查询模式很多时，可以建立一次索引，再为每次查询使用二分搜索。本课用前缀倍增构造，时间为 O(n log² n)。
索引保存位置而非后缀副本。例如 BANANA 中位置 3 代表后缀 ANA，数组只存六个起点，字符仍从原文本读取。位置索引占 O(n)，复制全部后缀则占 O(n²)。
后缀数组如何工作
长度 n 的文本中，后缀 i 为 text[i:]。BANANA 的排序结果是：
| SA 槽位 | 起点 | 后缀 |
|---|---|---|
| 0 | 5 | A |
| 1 | 3 | ANA |
| 2 | 1 | ANANA |
| 3 | 0 | BANANA |
| 4 | 4 | NA |
| 5 | 2 | NANA |
直接比较完整后缀容易实现，但一次比较可能检查 O(n) 个字符。前缀倍增把比较对象变成整数对。
先按字符赋秩，同一首字符的后缀得到相同秩。假设已有秩能区分前 k 个字符，那么后缀 i 的前 2k 个字符可表示为 (rank[i], rank[i + k])：前一项表示首个 k 字符块，后一项表示接下来的块。若第二块起点超过文本末尾，使用 -1，使短后缀排在共享相同前缀的长后缀之前，例如 A 排在 ANA 前面。
排序这些整数对，相同对赋相同新秩，相邻对改变时秩加一。新秩就能区分前 2k 字符。将 k 翻倍继续，所有秩唯一时后缀顺序确定。
查询用二分下界。比较模式与中间后缀的模式长度前缀：前缀较小就右移 lo，相等或较大就左移 hi。相等也向左，是因为要找匹配范围的左边界。区间闭合后再用一次 startswith 验证候选。
后缀数组逐步演示
默认先为 text = "BANANA" 建索引，再查 pattern = "ANA"。
- 字符顺序
A < B < N，秩为 0、1、2。按文本位置写回rank = [1, 0, 2, 0, 2, 0]。 k = 1：起点 0 的键为(1, 0)；1、3 为(0, 2)；2、4 为(2, 0)；5 为(0, -1)，因为单个 A 后已无字符。- 排序得到
[5, 1, 3, 0, 2, 4]。1、3 仍同秩，2、4 也同秩。按原起点写回的新秩为[2, 1, 3, 1, 3, 0]。 - 倍增到
k = 2。前一轮已区分两个字符。起点 1 的原始块为AN | AN，两个 AN 的秩都是 1，所以(1, 1)表示四字符前缀。全部键为：5 的(0, -1)、1 的(1, 1)、3 的(1, 0)、0 的(2, 3)、2 的(3, 3)、4 的(3, -1)。 - 再排序得到
[5, 3, 1, 0, 4, 2]。全部新秩唯一，构造停止。对应A, ANA, ANANA, BANANA, NA, NANA，无需另存这些字符串。 - 查询区间
[0, 6)，mid = 3指向文本起点 0，取前缀BAN。BAN > ANA，令hi = 3。 mid = 1指向起点 3，前缀为ANA。相等也令hi = 1，继续寻找左边界。mid = 0指向起点 5，前缀只有A。A < ANA，令lo = 1，此时lo == hi。SA[1] = 3，BANANA在索引 3 处确实以ANA开头，find_one返回 3。
ANA 也在文本索引 1 出现。返回 3 仍正确：函数返回的是后缀数组顺序中第一个匹配，不保证文本中的最小索引。要列出全部出现位置，可再求匹配前缀范围的右边界，收集区间内起点。
时间与空间复杂度
设文本长 n、模式长 m。
| 操作 | 时间 | 辅助空间 |
|---|---|---|
| 本课前缀倍增构造 | O(n log² n) | O(n) |
| 单次子串查询 | O(m log n) | O(m) 临时切片 |
| 保存后缀数组 | — | O(n) |
共有 O(log n) 轮，每轮构造 n 个常数大小的秩对，再用 O(n log n) 比较排序，因此总时间 O(n log² n)。改用整数秩的基数排序或计数排序可以达到 O(n log n)，但展示代码不是那个实现。
二分查询有 O(log n) 次探测，每次最多比较 m 个字符。教学代码切出前缀，会产生 O(m) 临时字符；直接按索引比较可省掉分配，不改变时间上界。
一个文本回答多次查询时，索引成本可由查询分摊。单次查询通常用 text.find(pattern)；同一模式用于多个持续到来的文本时，KMP 预处理的是模式这一侧。
边界情况
- 单字符文本只有一个后缀，初始秩已确定顺序，不进入倍增循环。
AAAAAAAA在k = 1, 2, 4保留同秩组，是画布八字符限制下最长的构造轨迹。- 后缀在第二块中结束：末尾哨兵
-1及前一轮块秩共同保证短后缀在前，不能用真实秩 0 代替越界哨兵。 - 模式比文本长：二分正常闭合，最终验证失败并返回
-1。 - 多次出现：
find_one返回后缀数组顺序中的一个位置，不一定是最小文本索引。 - 纯构造函数处理空文本，返回
SA = []；UI 要求文本和模式非空，因为空模式返回约定可能不同。
常见错误
- 存储所有
text[i:]副本，尚未构造就花掉 O(n²) 空间。后缀数组应存起点。 - 用 0 表示末尾。0 是实际字符类别的合法秩，哨兵必须小于所有真实秩。
- 计算新秩时原地修改
rank。同轮所有键必须读取相同旧数组，应写入next_rank后统一替换。 - 只比较
rank[i]，没有第二块就无法让已知前缀长度翻倍。 - 二分遇到相等就停止。可以找到一个匹配，但得不到下界；需要左边界时应保留
hi = mid。 - 将当前构造写成 O(n log n)。每轮使用比较排序，因此是 O(n log² n)，更快上界需要更换排序子程序。