在计算机科学里, 后缀数组(英語:suffix array)是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。
后缀数组被烏迪·曼伯爾(英语:Udi Manber)與尤金·邁爾斯(英语:Eugene Myers)于1990年提出,作为对后缀树的一种替代,更简单以及节省空间。它们也被Gaston Gonnet 于1987年獨立发現,并命名为「PAT数组」。
在2016年,李志泽,李建和霍红卫(页面存档备份,存于互联网档案馆)提出了第一个时间复杂度(线性时间)和空间复杂度(常数空间)都是最优的后缀数组构造算法,解决了该领域长达10年的open problem。
令字符串 S = S [ 1 ] S [ 2 ] . . . S [ n ] {\displaystyle S=S[1]S[2]...S[n]} , S [ i , j ] {\displaystyle S[i,j]} 表示 S {\displaystyle S} 的子字符串,下标从 i {\displaystyle i} 到 j {\displaystyle j} 。
S {\displaystyle S} 的后缀数组 A {\displaystyle A} 被定义为一个数组,内容是 S {\displaystyle S} 的所有后缀经过字典排序后的起始下标。
对于所有的有: 1 < i ≤ ≤ --> n {\displaystyle 1<i\leq n} : S [ A [ i − − --> 1 ] , n ] < S [ A [ i ] , n ] {\displaystyle S[A[i-1],n]<S[A[i],n]} 。
考虑字符串 S {\displaystyle S} =banana$:
banana$
字符串的结尾是特殊字符$,用作特殊标志。该字符串有以下后缀:
$
后缀经过升序排序后:
后缀数组 A {\displaystyle A} 包含这些后缀的起始位置: