{{Infobox
| above = 后缀数组
| label1 = 类型
| data1 = 数组
| label2 = 发明者
| data2 =
| header3 = 时间复杂度(大O符号)
| headerstyle = background:lavender
| data4 =
{{aligned table|cols=3|row1header=y|col1header=y|fullwidth=y
| | 平均 | 最坏情况
| 空间
| \mathcal{O}(n)
| \mathcal{O}(n)
| 构建
| \mathcal{O}(n)
| \mathcal{O}(n)
}}
}}
在计算机科学里, 后缀数组（英語：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。
后缀数组被與于1990年提出，作为对后缀树的一种替代，更简单以及节省空间。它们也被Gaston Gonnet 于1987年獨立发現，并命名为「PAT数组」。
在2016年，[http://arxiv.org/abs/1610.08305 李志泽，李建和霍红卫]提出了第一个时间复杂度（线性时间）和空间复杂度（常数空间）都是最优的后缀数组构造算法，解决了该领域长达10年的open problem。
定义
令字符串S=S[1]S[2]...S[n]， S[i,j]表示S的子字符串，下标从i到j。
S的后缀数组A被定义为一个数组，内容是S的所有后缀经过字典排序后的起始下标。
对于所有的有：1 : S[A[i-1],n] 。
例子
考虑字符串 S=banana$:
字符串的结尾是特殊字符$，用作特殊标志。该字符串有以下后缀：
后缀经过升序排序后：
后缀数组 A 包含这些后缀的起始位置：
外部链接
评论 (0)