更多：2011年軟考程序員考試復習筆試知識點整理匯總

　　21、后綴樹

　　后綴樹(Suffix tree)是一種數據結構，能快速解決很多關于字符串的問題。后綴樹提出的目的是用來支持有效的字符串匹配和查詢。

　　學習后綴樹之前，先了解一下Trie這個數據結構Trie是一種搜索樹，可用于存儲并查找字符串。Trie每一條邊都對應一個字符。在Trie中查找字符串S時，只要按順序枚舉S的各個字符，從Trie的根節點開始選擇相應的邊走，如果枚舉完的同時恰好走到Trie樹的葉子節點，說明S存在于Trie中。如果未到達葉子節點，或者枚舉中未發現相應的邊，則S沒有被包含在Trie中。

　　后綴樹就是一種壓縮后的Trie樹。

　　比如 S：banana，對S建立后綴樹。

　　首先給出S的后綴們

　　0：banana

　　1：anana

　　2：nana

　　3：ana

　　4：na

　　5：a

　　6：空

　　為了更清楚的表示后綴，我們在后綴的后面加上$

　　0：banana$

　　1：anana$

　　2：nana$

　　3：ana$

　　4：na$

　　5：a$

　　6：$

　　然后對其進行分類：

　　5:a$

　　3:ana$

　　1:anana$

　　0:banana$

　　4:na$

　　2:nana$

　　6: $

　　后綴樹的應用：

　　example 1：在樹中查找an(查找子字符串)

　　example 2：統計S中出現字符串T的個數

　　每出現一次T，都對應著一個不同的后綴，而這些后綴們又對應著同一個前綴T，因此這些后綴必定都屬于同一棵子樹，這棵子樹的分支數就是T在S中出現的次數。

　　example 3：找出S中最長的重復子串，所謂重復子串，是指出現了兩次以上。首先定義節點的“字符深度” = 從后綴樹根節點到每個節點所經過的字符串總長。找出有最大字符深度的非葉節點。則從根節點到該非葉節點所經過的字符串即為所求。

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)