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

　　10.多個(gè)串的公共子串問題 PKU3294

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

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

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

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

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

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

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

　　14、最后的總結(jié)

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

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

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

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

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

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

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

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

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

　　<3.2> 不重疊

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

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

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

　　[4] 特殊計(jì)數(shù)

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

　　[5] 重復(fù)問題

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

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

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

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