字尾陣列

在電腦科學里, 字尾陣列（英語：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實現的字尾陣列（頁面存檔備份，存於網際網路檔案館）