2011年軟考程序員考試復(fù)習(xí)筆試知識點整理(16)

　　10.多個串的公共子串問題 PKU3294

　　首先將串連接起來，然后構(gòu)造height數(shù)組，然后怎么辦呢?

　　對，二分答案再判斷是否可行就行了�？尚袟l件很直觀：有一組后綴，有超過題目要求的個數(shù)個不同的字符串中的后綴存在。即，假如題目要求要出現(xiàn)在至少k個串中，那么就得有一組后綴，在不同字符串中的后綴數(shù)大于等于k。

　　11、出現(xiàn)或反轉(zhuǎn)后出現(xiàn)所有字符串中的最長子串 PKU1226

　　12、不重疊地至少兩次出現(xiàn)在所有字符串中的最長子串

　　之所以把兩題一起說，因為它們大同小異，方法在前面的題目均出現(xiàn)過。對于多個串，連起來;反轉(zhuǎn)后出現(xiàn)，將每個字符串反寫后和原串都連起來，將反寫后的串和原串看成同一個串;求最長，二分答案后height分組;出現(xiàn)在所有字符串中(反寫后的也行)，判斷方法和10一樣，k=n而已;不重疊見問題4，只不過這里對于每個字符串都要進行檢驗而已。

　　13、兩個字符串的重復(fù)子串個數(shù)。 Pku3415

　　我個人覺得頗有難度的一個問題。具體的題目描述參看Pku3415。

　　14、最后的總結(jié)

　　用后綴數(shù)組解題有著一定的規(guī)律可循，這是后綴的性質(zhì)所決定的，具體歸納如下：

　　[1] N個字符串的問題(N>1)

　　方法：將它們連接起來，中間用不會出現(xiàn)在原串中的，互不相同的，非0號字符分隔開。

　　[2] 無限制條件下的最長公共子串(重復(fù)子串算是后綴們的最長公共前綴)

　　方法：height的最大值。這里的無限制條件是對子串無限制條件。最多只能是兩個串的最長公共子串，才可以直接是height的最大值。

　　[3] 特殊條件下的最長子串

　　方法：二分答案，再根據(jù)height數(shù)組進行分組，根據(jù)條件完成判定性問題。三個或以上的字符串的公共子串問題也需要二分答案。設(shè)此時要驗證的串長度為len，特殊條件有：

　　<3.1> 出現(xiàn)在k個串中

　　條件：屬于不同字符串的后綴個數(shù)不小于k。(在一組后綴中，下面省略)

　　<3.2> 不重疊

　　條件：出現(xiàn)在同一字符串中的后綴中，出現(xiàn)位置的最大值減最小值大于等于len。

　　<3.3> 可重疊出現(xiàn)k次

　　條件：出現(xiàn)在同一字符串中的后綴個數(shù)大于等于k。若對于每個字符串都需要滿足，需要逐個字符串進行判斷。

　　[4] 特殊計數(shù)

　　方法：根據(jù)后綴的性質(zhì)，和題目的要求，通過自己的思考，看看用后綴數(shù)組能否實現(xiàn)。一般和“子串”有關(guān)的題目，用后綴數(shù)組應(yīng)該是可以解決的。

　　[5] 重復(fù)問題

　　知道一點：lcp(i,i+k)可以判斷，以i為起點，長度為k的一個字符串，它向后自復(fù)制的長度為多少，再根據(jù)具體題目具體分析，得出算法即可。

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

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

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