後綴數組

後綴數組
類型	數組
發明者	Manber & Myers (1990)
時間複雜度(大O符號)
平均 最壞情況 空間 ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$ 構建 ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$

在計算機科學里, 後綴數組（英語：suffix array）是一個通過對字符串的所有後綴經過排序後得到的數組。此數據結構被運用於全文索引、數據壓縮算法、以及生物信息學。

後綴數組被烏迪·曼伯爾與尤金·邁爾斯於1990年提出，作為對後綴樹的一種替代，更簡單以及節省空間。它們也被Gaston Gonnet 於1987年獨立發現，並命名為「PAT數組」。

在2016年，李志澤，李建和霍紅衛（頁面存檔備份，存於網際網路檔案館）提出了第一個時間複雜度（線性時間）和空間複雜度（常數空間）都是最優的後綴數組構造算法，解決了該領域長達10年的open problem。

定義

令字符串$S=S[1]S[2]...S[n]$， $S[i,j]$表示$S$的子字符串，下標從$i$到$j$。

$S$的後綴數組$A$被定義為一個數組，內容是$S$的所有後綴經過字典排序後的起始下標。

對於所有的有：$1<i\leq n$: $S[A[i-1],n]<S[A[i],n]$。

例子

考慮字符串 $S$=banana$:

i	1	2	3	4	5	6	7
$S[i]$	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

後綴數組 $A$ 包含這些後綴的起始位置：

i	1	2	3	4	5	6	7
$A[i]$	7	6	4	2	1	5	3

外部連結

• Java實現的後綴數組（頁面存檔備份，存於網際網路檔案館）