Suffix tree—后綴樹

l  簡(jiǎn)介

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

l  定義

一個(gè)長(zhǎng)度為n的字符串S，它的后綴樹定義為一棵滿足如下條件的樹：

n  從根到樹葉的路徑與S的后綴一一對(duì)應(yīng)。即每條路徑惟一代表了S的一個(gè)后綴；

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

n  所有內(nèi)部節(jié)點(diǎn)（根節(jié)點(diǎn)除外）都有至少兩個(gè)子節(jié)點(diǎn)。

由于并非所有的字符串都存在這樣的樹，因此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ù)……