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

　　后綴樹的用途，總結起來大概有如下幾種 :

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

　　方案：用S構造后綴樹，按在trie中搜索字串的方法搜索o即可。

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

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

　　2. 指定字符串T在字符串S中的重復次數

　　方案：用S+'$'構造后綴樹，搜索T節(jié)點下的葉節(jié)點數目即為重復次數 。

　　原理：如果T在S中重復了兩次，則S應有兩個后綴以T為前綴，重復次數就自然統計出來了。

　　3. 字符串S中的最長重復子串

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

　　這個深是指從root所經歷過的字符個數，最深非葉節(jié)點所經歷的字符串起來就是最長重復子串。為什么要非葉節(jié)點呢?因為既然是要重復，當然葉節(jié)點個數要>=2。

　　4. 兩個字符串S1，S2的最長公共部分

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

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

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

　　后綴樹的構造：最簡單的方法，使用Trie的構造方法，時間復雜度為O(n^2);

　　后綴樹也可以在O(n)的時間復雜度內構造，但比較復雜。

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

　　算法所用符號描述：

　　后綴樹的構造，算法流程：

　　1)定義SL(root)=root，首先插入S，此時后綴樹僅有兩個節(jié)點。

　　2)設已經插入了S(i),現在要插入S(i+1)，分兩種情況討論：

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

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

　　不斷重復以上步驟，即可完成后綴樹的構造。

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

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

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