后缀数组 | Codeboy's Blog

形式陈述

取有全序的字母表，字符串 $T$ 长度为 $n\ge0$ ，后缀数组 $SA[0..n-1]$ 是起始位置的排列，使后缀 $T[SA[i]..]$ 按字典序严格递增排列；逆后缀数组 $ISA[p]$ 给起点 $p$ 的后缀在 $SA$ 中的秩。以模式 $P$ 为前缀的后缀形成连续区间，可分别二分其字典序下界与上界。对 $n\ge1$ 和非空模式，若每次比较至多检查 $|P|$ 个字符，两次二分最坏耗时 $O(|P|\log(n+1))$ ，再加实际报告位置的成本。空文本没有非空后缀；空模式按全部 $n+1$ 个文本边界单独报告，因为本页的 $SA$ 没有保存起点 $n$ 的空后缀。

直觉

后缀数组把一个字符串的所有后缀按字典序排列，并只保存起始位置。任意子串都是某个后缀的前缀；拥有共同模式前缀的后缀在数组中聚成连续区间，因此子串问题转为有序数组和区间问题，可用二分搜索。相邻后缀的公共前缀又由 LCP 数组压缩。相比后缀树，它表示紧凑、缓存友好，但查询需额外结构。

banana 加终止符的后缀数组及模式 ana 对应的连续区间 — 字典序后缀与模式区间

例子与边界

对附加最小且唯一终止符的 banana$，完整索引为：

$i$	$SA[i]$	后缀
0	6	`$`
1	5	`a$`
2	3	`ana$`
3	1	`anana$`
4	0	`banana$`
5	4	`na$`
6	2	`nana$`

这里 $ISA[3]=2$ ，因为 ana$ 位于第 $2$ 个秩；搜索模式 ana 时，下界与上界夹出 $SA[2..4)=\{3,1\}$ 。终止符小于其他字符且只出现一次，可统一前缀比较约定，但并非所有实现必需。相邻后缀的 LCP 值在本例为 $[0,0,1,3,0,0,2]$ ，它是由后缀序导出的独立数组，不属于 $SA/ISA$ 定义，也不自动附带区间最值结构。

不同起点的有限后缀长度不同，本来就彼此不同。附加唯一终止符进一步保证没有一个后缀是另一个的前缀，并可统一构造边界；索引必须说明终止符是否计入长度。直接复制全部后缀需要 $\Theta(n^2)$ 个字符，再用一般比较排序还须另计比较成本；只存起点虽然避免复制，长公共前缀仍可能让一次比较耗时 $\Theta(n)$ 。倍增或 SA-IS 等构造通过复用排名避免反复扫描。

推论与应用

词、数组与字典序定义结构，LCP 数组另行支持公共前缀与重复子串查询。倍增、诱导排序等构造及其工作空间由后缀数组构造分层说明；本页只把构造结果当作索引对象。

Burrows–Wheeler 变换可由后缀序导出，压缩后缀数组用简洁结构减少显式 $SA$ 空间，FM-index则在 BWT 上提供 backward search 与采样定位。它们分别改变表示和查询成本，不应被压成“后缀数组的一个实现细节”。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§32.5 “Suffix Arrays”。
Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997，§7.14 “Suffix Arrays — More Space Reduction”。

形式陈述 ​

反向链接

形式陈述