后缀数组
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
后缀数组 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
类型 | 数组 | |||||||||
发明者 | Manber & Myers (1990) | |||||||||
时间复杂度(大O符号) | ||||||||||
|
在计算机科学里, 后缀数组(英語: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 |
外部链接
|