后缀数组

在电脑科学里, 后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物资讯学。

后缀数组
类型	数组
发明者	Manber & Myers (1990) harvtxt模板错误: 无指向目标: CITEREFManberMyers1990 (帮助)
时间复杂度(大O符号)
平均 最坏情况 空间 ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$ 构建 ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$

后缀数组被乌迪·曼伯尔（英语：Udi Manber）与尤金·迈尔斯（英语：Eugene Myers）于1990年提出，作为对后缀树的一种替代，更简单以及节省空间。它们也被Gaston Gonnet 于1987年独立发现，并命名为“PAT数组”。

在2016年，李志泽，李建和霍红卫（页面存档备份，存于互联网档案馆）提出了第一个时间复杂度（线性时间）和空间复杂度（常数空间）都是最优的后缀数组构造算法，解决了该领域长达10年的open problem。

定义

令字符串${\displaystyle S=S[1]S[2]...S[n]}$， ${\displaystyle S[i,j]}$表示${\displaystyle S}$的子字符串，下标从${\displaystyle i}$到${\displaystyle j}$。

${\displaystyle S}$的后缀数组${\displaystyle A}$被定义为一个数组，内容是${\displaystyle S}$的所有后缀经过字典排序后的起始下标。

对于所有的有：${\displaystyle 1<i\leq n}$: ${\displaystyle S[A[i-1],n]<S[A[i],n]}$。

例子

考虑字符串 ${\displaystyle S}$=banana$:

i	1	2	3	4	5	6	7
${\displaystyle S[i]}$	b	a	n	a	n	a	$

字符串的结尾是特殊字符$，用作特殊标志。该字符串有以下后缀：

后缀	i
banana$	1
anana$	2
nana$	3
ana$	4
na$	5
a$	6
$	7

后缀经过升序排序后：

后缀	i
$	7
a$	6
ana$	4
anana$	2
banana$	1
na$	5
nana$	3

后缀数组 ${\displaystyle A}$ 包含这些后缀的起始位置：

i	1	2	3	4	5	6	7
${\displaystyle A[i]}$	7	6	4	2	1	5	3

外部链接

• Java实现的后缀数组（页面存档备份，存于互联网档案馆）