后缀数组 |
---|
类型 | 数组 |
---|
发明者 | Manber & Myers (1990) harvtxt模板錯誤: 無指向目標: CITEREFManberMyers1990 (幫助) |
---|
|
| 平均 | 最坏情况 |
---|
空间 | | |
---|
构建 | | |
---|
|
在计算机科学里, 后缀数组(英語:suffix array)是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。
后缀数组被烏迪·曼伯爾與尤金·邁爾斯于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
|
外部链接