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

　　7、求一個串最多由哪個串復制若干次得到 PKU2406

　　具體的問題描述請參考PKU2406.這個問題可以用KMP解決，而且效率比后綴數組好。

　　利用后綴數組直接解決本題也很困難(主要是，就算二分答案，也難以解決轉變而成的判定性問題。上題也是)，但可以同過枚舉模板串的長度k(模板串指被復制的那個串)將問題變成一個后綴數組可以解決的判定性問題。首先判斷k能否被n整除，然后只要看lcp(1,k+1)(實際在用c寫程序時是lcp(0,k))是否為n-k就可以了。

　　為什么這樣就行了呢?這要充分考慮到后綴的性質。當lcp(1，k+1)=n-k時，后綴k+1是后綴1(即整個字符串)的一個前綴。(因為后綴k+1的長度為n-k)那么，后綴1的前k個字符必然和后綴k+1的前k個字符對應相同。而后綴1的第k+1..2k個字符，又相當于后綴k+1的前k個字符，所以與后綴1的前k個字符對應相同，且和后綴k的k+1..2k又對應相同。依次類推，只要lcp(1,k+1)=n-k,那么s[1..k]就可以通過自復制n/k次得到整個字符串。找出k的最小值，就可以得到n/k的最大值了。

　　8、求兩個字符串的最長公共子串。Pku2774、Ural1517

　　首先區(qū)分好“最長公共子串”和“最長公共子序列”。前者的子串是連續(xù)的，后者是可以不連續(xù)的。

　　對于兩個字符串的問題，一般情況下均將它們連起來，構造height數組。然后，最長公共子串問題等價于后綴的最長公共前綴問題。只不過，并非所有的lcp值都能作為問題的答案。只有當兩個后綴分屬兩個字符串時，它們的lcp值才能作為答案。與問題3一樣，本題的答案必然是某個height值，因為lcp值是某段height值中的最小值。當區(qū)間長度為1時，lcp值等于某個height值。所以，本題只要掃描一遍后綴，找出后綴分屬兩個字符串的height值中的最大值就可以了。判斷方法這里就不說明了，留給大家自己思考...

　　9、重復次數最多的重復子串 SPOJ 687，Pku3693

　　難度比較大的一個問題，主要是羅穗騫的論文里的題解寫得有點含糊不清。題目的具體含義可以去參考Pku3693.

　　又是一題難以通過二分枚舉答案解決的問題(因為要求的是重復次數)，所以選擇樸素枚舉的方法。先枚舉重復子串的長度k，再利用后綴數組來求長度為k的子串最多重復出現多少次。注意到一點，假如一個字符串它重復出現2次(這里不討論一次的情況，因為那是必然的)，那么它必然包含s[0],s[k],s[2*k]...之中的相鄰的兩個。所以，我們可以枚舉一個數i，然后判斷從i*k這個位置起的長度為k的字符串能重復出現多少次。判斷方法和8中的相似，lcp(i*k,(i+1)*k)/k+1。但是，僅僅這樣會忽略點一些特殊情況，即重復子串的起點不在[i*k]位置上時的情況。這種情況應該怎么求解呢?看下面這個例子：

　　aabababc

　　當k=2，i=1時，枚舉到2的位置，此時的重復子串為ba(注意第一位是0),lcp(2，4)=3，所以ba重復出現了2次。但實際上，起始位置為1的字符串ab出現次數更多，為3次。我們注意到，這種情況下，lcp(2,4)=3，3不是2的整數倍。說明當前重復子串在最后沒有多重復出現一次，而重復出現了部分(這里是多重復出現了一個b)。如果我這樣說你沒有看懂，那么更具體地：

　　sa[2]=bababc

　　sa[4]=babc

　　lcp=bab

　　現在注意到了吧，ba重復出現了兩次之后，出現了一個b，而a沒有出現。那么，不難想到，可以將枚舉的位置往前挪一位，這樣這個最后的b就能和前面的一個a構成一個重復子串了，而假如前挪的一位正好是a，那么答案可以多1。所以，我們需要求出a=lcp(i*k,(i+1)*k)%n，然后向前挪k-a位，再用同樣的方法求其重復出現的長度。這里，令b=k-a,只需要lcp(b,b+k)>=k就可以了。實際上，lcp(b,b+k)>=k時，lcp(b,b+k)必然大于等于之前求得的lcp值，而此時答案的長度只加1。沒有理解的朋友細細體會下上圖吧。

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

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

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