后缀数组

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

后缀数组
类型数组
发明者Manber & Myers (1990)
时间复杂度(大O符号)
平均 最坏情况
空间
构建

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

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

定义

令字符串  表示 的子字符串,下标从  

 的后缀数组 被定义为一个数组,内容是 的所有后缀经过字典排序后的起始下标。

对于所有的有: :  


例子

考虑字符串  =banana$:

i 1 2 3 4 5 6 7
  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

后缀数组   包含这些后缀的起始位置:

i 1 2 3 4 5 6 7
  7 6 4 2 1 5 3

外部链接