后缀数组

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

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

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

必须明确是否附加全局最小终止符；它能保证所有后缀不同并简化构造。直接存完整后缀并排序会产生 $O(n^2)$ 数据和比较成本，倍增或 SA-IS 等算法利用排名避免这一退化。

词公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。、数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。与字典序公理库全序Total order · Linear order任意两个元素都可比较的偏序。定义结构，LCP 数组公理库LCP 数组Longest common prefix array · Height array按后缀数组顺序记录相邻后缀最长公共前缀长度的数组。另行支持公共前缀与重复子串查询。倍增、诱导排序等构造及其工作空间由后缀数组构造公理库后缀数组构造算法Suffix array construction · SA construction · 后缀数组构造以逐轮秩细化统一 doubling、DC3/Skew 与 SA-IS 路线，并按比较模型或整数 Word-RAM 分别报告构造时间和工作空间。分层说明；本页只把构造结果当作索引对象。

Burrows–Wheeler 变换公理库Burrows–Wheeler 变换Burrows-Wheeler transform · BWT对带唯一终止符文本的循环移位排序，并取最后一列形成可逆排列。可由后缀序导出，压缩后缀数组公理库压缩后缀数组Compressed suffix array · CSA用 Ψ/LF 排列、简洁导航和 SA/ISA 稀疏采样压缩显式后缀数组，并以采样步长换取 access 与 locate 时间。用简洁结构减少显式 $SA$ 空间，FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。则在 BWT 上提供 backward search 与采样定位。它们分别改变表示和查询成本，不应被压成“后缀数组的一个实现细节”。