Suffix tree—后綴樹

l  簡介

后綴樹是一種PAT樹，它描述了給定字符串的所有后綴，許多重要的字符串操作都能夠在后綴樹上快速地實現。

l  定義

一個長度為n的字符串S，它的后綴樹定義為一棵滿足如下條件的樹：

n  從根到樹葉的路徑與S的后綴一一對應。即每條路徑惟一代表了S的一個后綴；

n  每條邊都代表一個非空的字符串；

n  所有內部節點（根節點除外）都有至少兩個子節點。

由于并非所有的字符串都存在這樣的樹，因此S通常使用一個終止符號進行填充（通常使用$）。

l  優點

n  匹配快。對于長度為m的模式串，只需花費至多O(m)的時間進行匹配。

n  空間省。Suffix tree的空間耗費要低于Suffix trie，因為Suffix tree除根節點外不允許其內部節點只含單個子節點，因此它是Suffix trie的壓縮表示。

待續……