後綴樹

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

單詞BANANA的後綴樹。$為終止符。從根到葉的六條路徑（方框裏）對應六個後綴：A$、NA$、ANA$、NANA$、ANANA$和BANANA$。葉子中的數字表示出現的起點位置。後綴鏈用點線畫出

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