最長重復子串

1、最長重復子串最長重復子串湖南長沙市雅禮中學湖南長沙市雅禮中學龍凡龍凡【關鍵詞關鍵詞】擴展擴展KMPKMP算法算法二分二分后綴數組后綴數組后綴樹后綴樹【引言引言】近些年來，字符串類型的試題越來越多的出現在信息學競賽中。而字符串處理中常常出現的一類問題即——最長重復子串。本文將討論最長重復子串問題及它的幾種變形，并給出實際應用中效果較好的解決該類問題的幾種方法。文中將涉及到使用擴展KMP、后綴數組等工具性算法。這些算法的具體方法與實現請參考

2、近年來的國家集訓隊論文。【連續(xù)最長重復子串連續(xù)最長重復子串】1.問題描述給定一個長度為N的字符串S。記為S的第I個字符到第J個字)(jis)(nji??符所組成的子串。若存在，則稱S存在一個長度為K的)12()1(??????kikiskiis連續(xù)重復子串?，F在要你求出K的最大值，滿足存在一個值I使得。)12()1(??????kIkiskiis2.基于二分的算法枚舉K，然后掃描的方法的時間復雜度高達O(N2)，效果并不能讓人滿意。我們

3、需要更高效的算法，這里給出一個基于二分結合擴展KMP算法的算法，時間復雜度為O(Nlog2N)。在介紹主算法之前，我們先來簡要介紹擴展KMP算法，這里并不對擴展KMP算法具體如何實現進行介紹，僅僅為了方便讀者理解，介紹擴展KMP算法的功能。具體的擴展KMP算法的實現，請參考2003年國家集訓隊林希德的論文。擴展KMP算法：對于一個主串S，和一個模式串T。記。而擴展KMP算法可以在O(Len(S)Len(T))時間復雜)1()1(max)

4、(ktkiiskiq????度內求解q(1)…q(len(s))?，F在回到主算法，對于一個給定的串S。設Ans(S)為該串的連續(xù)最長重復子串長度。那么可以知道：)())1(())((max))((rlCrossrsAnslsAnsrlsAns??其中Cross(lr)表示：在s(lr)中，包含s()和s(1)這兩個字符的連續(xù)最長重復子串長度。根據上面的性質，我們二分求解Ans(S(lr))，令。如????????2rl兩種情況的時間復雜

5、度為O(rl)。那么如何預先算出West數組和East數組呢？通過分析我們發(fā)現：設Rotate(S)表示S字符串的逆字符串：比如Rotate(‘123’)=Rotate(‘321’)。則West數組事實上是Rotate(s(lr))作為母串，Rotate(s(l))作為模式串時，擴展KMP算法求得的Q數組。而East數組則是S(lr)作為母串，s(1r)作為模式串時，擴展KMP算法求得的Q數組。我們只要預先執(zhí)行兩次擴展KMP算法，就能在

6、O(rl)的時間復雜度內求得West數組和East數組。那么我們計算Css(lr)的時間復雜度也為O(rl)，也就是說我們可以利用二分配合擴展KMP算法在O(Nlog2N)的時間復雜度內求得Ans(S(1n))，即我們要求的答案。3.其他解決方法上面，我們給出了O(Nlog2N)的時間復雜度內利用二分＋擴展KMP求解連續(xù)最長重復子串的算法。事實上，這道題目利用后綴樹配合擴展KMP，可以在O(NLog2Σ)的時間復雜度內解決（其中Σ是字符

7、串涉及的字符集大?。?。由于后綴樹實現較為復雜，并且對空間要求較高，這里就不作介紹了。有興趣的讀者可以參考2003年國家集訓隊員林希德的論文?！具B續(xù)重復子串的擴展連續(xù)重復子串的擴展】1問題的擴展給出一個長度為N的字符串S以及整數g。有多少對不同的i、j使得：，且。)12()1(????????gkigkiSkiiS112?????kjgki題目來源：UVA10829LGapSubstring，原題1050000??gN2算法分析這道題目相

8、比經典的連續(xù)最長重復子串問題，有兩點不同：1.題目中有一個g的參量，這個參量的意義相當于兩個重復子串之間的間隔長度。當g=0時即連續(xù)重復子串。2.題目需要我們給出的是長度大于1的重復子串的個數，而不是最長重復子串的長度。我們仍然嘗試使用二分配合擴展KMP算法的方法來求解該問題。設Ans(s)為字符串為字符串S滿足題目條件的重復子串個數滿足題目條件的重復子串個數。和連續(xù)重復子串經典問題一樣，我們有：)())1(())(())((rlCro