後綴樹
外觀
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Suffix_tree_BANANA.svg/250px-Suffix_tree_BANANA.svg.png)
BANANA
的後綴樹。$
為終止符。從根到葉的六條路徑(方框裡)對應六個後綴:A$
、NA$
、ANA$
、NANA$
、ANANA$
和BANANA$
。葉子中的數字表示出現的起點位置。後綴鏈用點線畫出後綴樹(英語:Suffix tree)是一種數據結構,能快速解決很多關於字符串的問題。後綴樹的概念最早由Weiner於1973年提出,既而由McCreight在1976年和Ukkonen在1992年和1995年加以改進完善。
一個string S的後綴樹是一個邊(edge)被標記為字符串的樹。因此每一個S的後綴都唯一對應一條從根節點到葉節點的路徑。這樣就形成了一個S的後綴的基數樹(radix tree)。後綴樹是前綴樹(trie)里的一個特殊類型。
|
|
![]() | 這是一篇與電腦相關的小作品。您可以透過編輯或修訂擴充其內容。 |