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

　　后綴樹(shù)的用途，總結(jié)起來(lái)大概有如下幾種 :

　　1. 查找字符串o是否在字符串S中

　　方案：用S構(gòu)造后綴樹(shù)，按在trie中搜索字串的方法搜索o即可。

　　原理：若o在S中，則o必然是S的某個(gè)后綴的前綴。

　　聽(tīng)起來(lái)有點(diǎn)拗口，舉個(gè)例子。例如S: leconte，查找o: con是否在S中,則o(con)必然是S(leconte)的后綴之一conte的前綴。有了這個(gè)前提，采用trie搜索的方法就不難理解了。

　　2. 指定字符串T在字符串S中的重復(fù)次數(shù)

　　方案：用S+'$'構(gòu)造后綴樹(shù)，搜索T節(jié)點(diǎn)下的葉節(jié)點(diǎn)數(shù)目即為重復(fù)次數(shù) 。

　　原理：如果T在S中重復(fù)了兩次，則S應(yīng)有兩個(gè)后綴以T為前綴，重復(fù)次數(shù)就自然統(tǒng)計(jì)出來(lái)了。

　　3. 字符串S中的最長(zhǎng)重復(fù)子串

　　方案：原理同2，具體做法就是找到最深的非葉節(jié)點(diǎn)。

　　這個(gè)深是指從root所經(jīng)歷過(guò)的字符個(gè)數(shù)，最深非葉節(jié)點(diǎn)所經(jīng)歷的字符串起來(lái)就是最長(zhǎng)重復(fù)子串。為什么要非葉節(jié)點(diǎn)呢?因?yàn)榧热皇且貜?fù)，當(dāng)然葉節(jié)點(diǎn)個(gè)數(shù)要>=2。

　　4. 兩個(gè)字符串S1，S2的最長(zhǎng)公共部分

　　方案：將S1#S2$作為字符串壓入后綴樹(shù)，找到最深的非葉節(jié)點(diǎn)，且該節(jié)點(diǎn)的葉節(jié)點(diǎn)既有#也有$(無(wú)#)。大體原理同3。

　　//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

　　后綴樹(shù)的存儲(chǔ)：為了節(jié)省空間，我們不在邊上存儲(chǔ)字符串，而是存儲(chǔ)該字符串在原串中的起止位置，空間復(fù)雜度O(n)。

　　后綴樹(shù)的構(gòu)造：最簡(jiǎn)單的方法，使用Trie的構(gòu)造方法，時(shí)間復(fù)雜度為O(n^2);

　　后綴樹(shù)也可以在O(n)的時(shí)間復(fù)雜度內(nèi)構(gòu)造，但比較復(fù)雜。

　　如，基本思路：先向后綴樹(shù)中插入最長(zhǎng)的后綴串(S本身)，其次插入次長(zhǎng)的后綴串，以此類推，最后插入空串。定義后綴鏈接(Suffix Link)=從節(jié)點(diǎn)A指向節(jié)點(diǎn)B的指針，B所表示的子串是A所表示的子串的最長(zhǎng)后綴。既，根節(jié)點(diǎn)到A所經(jīng)過(guò)的字符串s=aw，則從根節(jié)點(diǎn)到B所經(jīng)過(guò)的字符串為w。

　　算法所用符號(hào)描述：

　　后綴樹(shù)的構(gòu)造，算法流程：

　　1)定義SL(root)=root，首先插入S，此時(shí)后綴樹(shù)僅有兩個(gè)節(jié)點(diǎn)。

　　2)設(shè)已經(jīng)插入了S(i),現(xiàn)在要插入S(i+1)，分兩種情況討論：

　　1：P(S(i))在插入之前已經(jīng)存在，(如，na，ana，a是na的parent)，則P(S(i))有后綴鏈接，令u=SL(P(S(i)))，從u開(kāi)始沿著樹(shù)往下查找，在合適的地方插入。

　　2：P(S(i))是插入S(i)過(guò)程中產(chǎn)生的，此時(shí)G(S(i))必定存在并有后綴鏈接，比如(na，ana，bana)，令u=SL(G(S(i)))，w=W(G(S(i)),P(S(i))).從u開(kāi)始，對(duì)w進(jìn)行快速定位， 在合適的地方插入新的節(jié)點(diǎn)。

　　不斷重復(fù)以上步驟，即可完成后綴樹(shù)的構(gòu)造。

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

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

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