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