2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(17)

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理匯總

　　21、后綴樹

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

　　學(xué)習(xí)后綴樹之前，先了解一下Trie這個(gè)數(shù)據(jù)結(jié)構(gòu)Trie是一種搜索樹，可用于存儲(chǔ)并查找字符串。Trie每一條邊都對(duì)應(yīng)一個(gè)字符。在Trie中查找字符串S時(shí)，只要按順序枚舉S的各個(gè)字符，從Trie的根節(jié)點(diǎn)開始選擇相應(yīng)的邊走，如果枚舉完的同時(shí)恰好走到Trie樹的葉子節(jié)點(diǎn)，說明S存在于Trie中。如果未到達(dá)葉子節(jié)點(diǎn)，或者枚舉中未發(fā)現(xiàn)相應(yīng)的邊，則S沒有被包含在Trie中。

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

　　比如 S：banana，對(duì)S建立后綴樹。

　　首先給出S的后綴們

　　0：banana

　　1：anana

　　2：nana

　　3：ana

　　4：na

　　5：a

　　6：空

　　為了更清楚的表示后綴，我們?cè)诤缶Y的后面加上$

　　0：banana$

　　1：anana$

　　2：nana$

　　3：ana$

　　4：na$

　　5：a$

　　6：$

　　然后對(duì)其進(jìn)行分類：

　　5:a$

　　3:ana$

　　1:anana$

　　0:banana$

　　4:na$

　　2:nana$

　　6: $

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

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

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

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

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

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

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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