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

　　首先將串連接起來，然后構造height數組，然后怎么辦呢?

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

　　11、出現或反轉后出現所有字符串中的最長子串 PKU1226

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

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

　　13、兩個字符串的重復子串個數。 Pku3415

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

　　14、最后的總結

　　用后綴數組解題有著一定的規律可循，這是后綴的性質所決定的，具體歸納如下：

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

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

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

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

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

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

　　<3.1> 出現在k個串中

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

　　<3.2> 不重疊

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

　　<3.3> 可重疊出現k次

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

　　[4] 特殊計數

　　方法：根據后綴的性質，和題目的要求，通過自己的思考，看看用后綴數組能否實現。一般和“子串”有關的題目，用后綴數組應該是可以解決的。

　　[5] 重復問題

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

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

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

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