2011年軟考程序員考試復習筆試知識點整理(17)

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

　　21、后綴樹

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

　　學習后綴樹之前，先了解一下Trie這個數(shù)據(jù)結(jié)構(gòu)Trie是一種搜索樹，可用于存儲并查找字符串。Trie每一條邊都對應(yīng)一個字符。在Trie中查找字符串S時，只要按順序枚舉S的各個字符，從Trie的根節(jié)點開始選擇相應(yīng)的邊走，如果枚舉完的同時恰好走到Trie樹的葉子節(jié)點，說明S存在于Trie中。如果未到達葉子節(jié)點，或者枚舉中未發(fā)現(xiàn)相應(yīng)的邊，則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: $

　　后綴樹的應(yīng)用：

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

　　example 2：統(tǒng)計S中出現(xiàn)字符串T的個數(shù)

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

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

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

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

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