跳至內容

後綴樹

維基百科,自由的百科全書
單詞BANANA的後綴樹。$為終止符。從根到葉的六條路徑(方框裏)對應六個後綴:A$NA$ANA$NANA$ANANA$BANANA$。葉子中的數字表示出現的起點位置。後綴鏈用點線畫出

後綴樹(英語:Suffix tree)是一種數據結構,能快速解決很多關於字符串的問題。後綴樹的概念最早由Weiner於1973年提出,既而由McCreight在1976年和Ukkonen在1992年和1995年加以改進完善。

一個string S的後綴樹是一個邊(edge)被標記為字符串的樹。因此每一個S的後綴都唯一對應一條從根節點到葉節點的路徑。這樣就形成了一個S的後綴的基數樹(radix tree)。後綴樹是前綴樹(trie)里的一個特殊類型。