后缀数组
在计算机科学里, 后缀数组(英语:suffix array)是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。
后缀数组 | ||
---|---|---|
类型 | 数组 | |
发明者 | Manber & Myers (1990) | |
时间复杂度(大O符号) | ||
平均 | 最坏情况 | |
空间 | ||
构建 |
后缀数组被乌迪·曼伯尔与尤金·迈尔斯于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 |
外部链接
- Java实现的后缀数组(页面存档备份,存于互联网档案馆)