后缀数组

定义

后缀数组(Suffix Array)是字符串所有后缀按字典序排序后的起始下标数组,由 Udi Manber 与 Gene Myers 于 1990 年提出,作为后缀树的省空间替代。

构造

经典倍增算法按长度 1、2、4……的前缀对后缀反复基数排序,复杂度 O(n log n);SA-IS 等诱导排序算法可达线性时间。配套的 LCP 数组(相邻后缀的最长公共前缀)可用 Kasai 算法在 O(n) 内求出。

应用

任意子串查找(在排序后缀上二分,O(m log n))、最长重复子串与最长公共子串、不同子串计数、全文索引与搜索引擎、生物信息学基因组比对(BWA 等工具基于其近亲 FM-index/BWT)、数据压缩(Burrows-Wheeler 变换)。

优缺点

相比后缀树空间小、缓存友好、实现相对简单;缺点是不如后缀树直观,动态更新(增删字符)支持较弱,通常面向静态文本。