後綴數組

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

後綴數組
類型	數組
發明者	Manber & Myers (1990) harvtxt模板錯誤: 無指向目標: CITEREFManberMyers1990 (幫助)
時間複雜度(大O符號)
平均 最壞情況 空間 ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$ 構建 ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$

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

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

定義

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

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

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

例子

考慮字符串 ${\displaystyle S}$=banana$:

i	1	2	3	4	5	6	7
${\displaystyle 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

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

i	1	2	3	4	5	6	7
${\displaystyle A[i]}$	7	6	4	2	1	5	3

外部連結

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