后缀数组

在计算机科学里, 后缀数组（英語：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

 外部链接 
 Java实现的后缀数组

Category:数组
Category:子字符串索引
Category:字符串数据结构