后缀数组构造算法

输入约定与输出 ​

给文本 $T[0..n)$ 追加唯一且全局最小的终止符 $\mathrm{\$}$。目标输出后缀数组公理库后缀数组Suffix array按字典序排列字符串全部后缀起始位置的数组索引。 $SA$，使 $T[SA[i]..]$ 按字典序递增；同时可构造逆数组 $ISA$。

字符必须有固定全序。线性整数算法通常进一步要求字母表已编码为 $[0,\sigma )$、$\sigma =O(n)$，字符和下标能装入一个 $w=\mathrm{\Omega }(\log n)$ 的 word，并允许线性时间 bucket/counting sort。若只有任意对象比较器，不能免费获得这套整数模型。

终止符既让所有后缀互异，也为越过文本末尾的排名提供统一最小哨兵。若输入本身可能含 $，必须先重编码或选择域外符号。

Doubling：按 $2^k$ 前缀细化秩 ​

初始按单字符给每个后缀排名 $ran{k}_0[i]$。第 $k$ 轮已知长度 $2^k$ 前缀的秩后，长度 $2^{k+1}$ 前缀由秩对

$$(ran{k}_k[i],ran{k}_k[i+2^k])$$

完全决定；越界的第二项记为 $-1$。稳定排序所有秩对，再把相等对压成相同新秩。若秩已全部不同，当前顺序就是最终 $SA$。

每轮覆盖长度翻倍，共 $O(\log n)$ 轮。秩位于 $[0,n)$，用两遍稳定 基数/计数排序公理库基数排序Radix sort按稳定子程序逐位处理固定长度键的非比较排序。可令每轮 $O(n)$，总时间 $O(n\log n)$、工作空间 $O(n)$ words。若每轮用比较排序，时间会变成 $O(n{\log }^{2}n)$，不能仍引用整数排序版本的界。

banana$ 的两轮轨迹 ​

对 banana$，按字符序 $ < a < b < n 取秩，初始

$$ran{k}_0=[2,1,3,1,3,1,0].$$

排序长度 $2$ 的秩对后，后缀起点次序为

$$(6,5,1,3,0,2,4),$$

其中起点 $1,3$ 的前缀都是 an，起点 $2,4$ 的前缀都是 na，仍共享秩。再按长度 $4$ 的对排序，得到

$$SA=(6,5,3,1,0,4,2),$$

所有秩已唯一，对应 $,a$,ana$,anana$,banana$,na$,nana$。这个轨迹展示“排序完整后缀”被有限整数秩对替代。

DC3/Skew 的差分覆盖 ​

DC3 把起点按模 $3$ 分组，先递归排序位置 $imod3\ne 0$ 的后缀；这些位置形成 difference cover，使相关后缀比较可由常数个已知秩完成。随后对 $imod3=0$ 的后缀作 bucket sort，并线性归并两组顺序。

若抽出的三字符元组排名仍不唯一，就递归排序缩短后的秩串。每层总输入规模按常数比例缩小，bucket 操作为线性，因而在整数 Word-RAM 模型中得到 $O(n)$ 时间与 $O(n)$ words 工作空间。

稳定排序是证明的一部分：相同前缀键必须保留用于下一关键字的既有次序。把 DC3 的线性归并换成任意字符串比较，会重新引入长前缀扫描。

SA-IS 的诱导排序 ​

SA-IS 从右向左把位置分成 S-type 与 L-type，并选取从 L 到 S 转折的 LMS 位置。先按首字符 bucket 放置 LMS 后缀，再从已放位置诱导 L 后缀、反向诱导 S 后缀。

相邻 LMS 子串被命名成新整数串；若名称不唯一，就递归求这个更短串的后缀数组，再按所得 LMS 次序执行最终诱导。LMS 数至多约 $n/2$，各层扫描和 bucket 操作线性，得到整数模型下 $O(n)$ 时间。

“S/L 类型”取决于后缀字典序而不只取决于相邻字符；相等字符时类型继承右邻。分类或 bucket 端点错一位，会让诱导阶段静默丢失后缀。

模型与算法选择 ​

Doubling 结构简单，易复用稳定整数排序；DC3 与 SA-IS 达到理论线性，却有更复杂的递归、bucket 与工作区管理。线性界不表示它们在所有输入规模上更快。

任意比较字母表至少要付出建立字符秩和比较信息的成本。若字符是长对象或 locale-sensitive 字符串，先把它们压成整数也可能需要 $O(n\log n)$ 比较；此时“SA-IS 为线性”只覆盖压缩后的阶段。

输出 $SA$ 本身需要 $n\lceil \log n\rceil$ bits，构造峰值空间还可能含多个 rank、bucket 和临时数组。最终索引空间与构建工作空间不能混为一项。

失败边界与相邻结构 ​

直接物化每个后缀再比较会产生 $\mathrm{\Theta }(n^2)$ 字符数据；即使只存起点，朴素比较也可能反复扫描长公共前缀。秩细化的核心正是让已知相等前缀只用整数代表。

LCP 数组公理库LCP 数组Longest common prefix array · Height array按后缀数组顺序记录相邻后缀最长公共前缀长度的数组。、BWT公理库Burrows–Wheeler 变换Burrows-Wheeler transform · BWT对带唯一终止符文本的循环移位排序，并取最后一列形成可逆排列。与FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。以构造好的后缀序为输入或邻近结构，不属于 SA 构造步骤本身。在线文本追加也会改变大量后缀次序，静态构造算法不能局部套用。

参考资料

• Udi Manber and Gene Myers, “Suffix Arrays: A New Method for On-Line String Searches,” SIAM Journal on Computing 22(5), 1993.
• Juha Kärkkäinen and Peter Sanders, “Simple Linear Work Suffix Array Construction,” ICALP, 2003.
• Ge Nong, Sen Zhang, and Wai Hong Chan, “Linear Suffix Array Construction by Almost Pure Induced-Sorting,” DCC, 2009.