最長重復(fù)子串

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

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

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

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

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

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

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

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