跳至內容

後綴數組

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
後綴數組
類型數組
發明者Manber & Myers (1990)
時間複雜度(大O符號)
平均 最壞情況
空間
構建

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

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

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

定義

令字符串表示的子字符串,下標從

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

對於所有的有::


例子

考慮字符串 =banana$:

i 1 2 3 4 5 6 7
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

後綴數組 包含這些後綴的起始位置:

i 1 2 3 4 5 6 7
7 6 4 2 1 5 3

外部連結