說到后綴樹，我相信很多人通過名字看出來樹是一種結(jié)構(gòu)形態(tài)，后綴樹就是帶后綴的結(jié)構(gòu)，后綴，顧名思義，甚至通俗點(diǎn)來說，就是所謂后綴就是后面尾巴的意思。比如說給定一長度為n的字符串S=S1S2..Si..Sn，和整數(shù)i，1≤i≤n，子串SiSi+1...Sn便都是字符串S的后綴。當(dāng)然這樣只是通過文字形式上的理解，不夠全面，下面我們來看看具體的定義和表現(xiàn)形式吧。

什么是后綴樹？

后綴樹是一種數(shù)據(jù)結(jié)構(gòu)，能快速解決很多關(guān)于字符串的問題。后綴樹的概念最早由Weiner于1973年提出，既而由McCreight在1976年和Ukkonen在1992年和1995年加以改進(jìn)完善。

一個(gè)string S的后綴樹是一個(gè)邊（edge）被標(biāo)記為字符串的樹。因此每一個(gè)S的后綴都唯一對(duì)應(yīng)一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑。這樣就形成了一個(gè)S的后綴的基數(shù)樹（radix tree）。后綴樹是前綴樹（trie）里的一個(gè)特殊類型。

后綴樹的定義：長度為m的序列S，其后綴樹是一個(gè)有向樹，滿足以下條件：

（1）有m個(gè)葉結(jié)點(diǎn)； 

（2）除了根結(jié)點(diǎn)和葉結(jié)點(diǎn)，每一個(gè)內(nèi)部結(jié)點(diǎn)至少有兩條邊（子節(jié)點(diǎn)），每條邊對(duì)應(yīng)S中的一個(gè)非空序列；

（3）從任何一個(gè)內(nèi)部結(jié)點(diǎn)出發(fā)的兩條邊對(duì)應(yīng)的字符串序列的第一個(gè)字符都不相同；

（4）從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑上的字符序列構(gòu)成了S從i開始的一個(gè)后綴字符串；

路徑標(biāo)簽：一個(gè)路徑上對(duì)應(yīng)的字符序列稱為路徑標(biāo)簽；

結(jié)點(diǎn)標(biāo)簽：從根結(jié)點(diǎn)開始到此結(jié)點(diǎn)對(duì)應(yīng)的路徑的標(biāo)簽稱為結(jié)點(diǎn)標(biāo)簽；

并不是所有的字符序列都有后綴樹，例如xabxa（其后綴有xabxa，abxa，bxa，xa，a）xa為xabxa的前綴，為了解決此問題，通常在字符串末尾加上$符號(hào)，使得任何一個(gè)后綴都不為其他后綴的前綴。

 注：從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)路徑上的字符（詞）表示對(duì)應(yīng)葉節(jié)點(diǎn) i 開始的某一個(gè)后綴字符串，葉子結(jié)點(diǎn)存儲(chǔ)了起始位置 i 有幾個(gè)字符（詞）就有幾個(gè)葉子結(jié)點(diǎn)，根結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)不存儲(chǔ)任何數(shù)據(jù)，只有葉子結(jié)點(diǎn)和邊存儲(chǔ)數(shù)據(jù)；

雖然本篇的文字內(nèi)容不是很多，但是卻用最直觀的形式進(jìn)行講解，不知道大家看完后，有沒有形成一套知識(shí)體系呢？