Suffix tree—后綴樹
l 簡介
后綴樹是一種PAT樹，它描述了給定字符串的所有后綴，許多重要的字符串操作都能夠在后綴樹上快速地實現(xiàn)。
l 定義
一個長度為n的字符串S，它的后綴樹定義為一棵滿足如下條件的樹：
n 從根到樹葉的路徑與S的后綴一一對應。即每條路徑惟一代表了S的一個后綴；
n 每條邊都代表一個非空的字符串；
n 所有內(nèi)部節(jié)點（根節(jié)點除外）都有至少兩個子節(jié)點。
由于并非所有的字符串都存在這樣的樹，因此S通常使用一個終止符號進行填充（通常使用$）。
l 優(yōu)點
n 匹配快。對于長度為m的模式串，只需花費至多O(m)的時間進行匹配。
n 空間省。Suffix tree的空間耗費要低于Suffix trie，因為Suffix tree除根節(jié)點外不允許其內(nèi)部節(jié)點只含單個子節(jié)點，因此它是Suffix trie的壓縮表示。
待續(xù)……