字尾陣列

字尾陣列
類型	陣列
發明者	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實現的字尾陣列（頁面存檔備份，存於網際網路檔案館）