轉自：https://www.cse.msu.edu/~liyang5/?p=53

《編程珠璣》在第15章“珍珠字符串”一節，給出了一個非常漂亮的實現 – 基于目標字符串的后綴數組的實現。

后綴數組類似于后綴樹，但是又有所不同。
后綴樹常用來查找某一段文字中是否出現過（多個）模式串，通過對目標文字段預處理建立后綴樹實現。（如果你不明白，參考本blog有一個 字符串模式匹配總結的文章，里面有一篇參考文章將后綴樹）。
也可以參考如下文章。
后綴樹學習?– [ACM]
http://kinslovertec.blogbus.com/logs/43784965.html?
（等等，有個疑問，前綴樹是什么？ 哦，前綴樹就是自動機了。字符串多模式匹配中的AC自動機就是一例）

后綴數組舉例 如下目標字符串： banana 其長度為6，則后綴數組的長度為6，分別是以b開頭的字串（長度為6），以a開頭的字串（長度為5），以n開頭的字串（長度為4）。。。最后一個是以a開頭的字串（長度為1）。
后綴[0] banana
后綴[1] anana
后綴[2] nana
后綴[3] ana
后綴[4] na
后綴[5] a

回到正題，查找一段文字中最長的重復字串。（注意：這不同于算法設計課中常講的兩個字符串的最長公共子序列問題（LCS），LCS問題的最長公共字串可以不是連續的）
最 樸素的算法是，讓后綴數組之間兩兩比較，找出最長的公共字串(注意，這里的最長的公共字串必須是以首字符參與匹配的，如果首字母都不匹配，那么長度為 0，eg后綴[0]和后綴[1]之間的首字母不匹配，則兩者的最長公共字串長度為0.。)，但是時間復雜度為O(n^2).

該思想基于以下兩個信息：
1）如果存在一個最長的重復字串，那么兩個字串均是來自文本串不同的后綴，但這兩個后綴有相同的前綴！（這個前綴也就是重復字串了）
2）既然最終結果的后綴肯定擁有相同的前綴，那么我就沒有必要讓全部后綴之間兩兩比較，而僅僅比較具有相同的前綴的后綴即可！這可以大大的減少比較的次數，提高效率。

所以，算法的流程是，先將后綴數組字母排序，然后順次比較（避免了兩兩比較）即可。
后綴[0] a
后綴[1]?ana
后綴[2]?anana
后綴[3] banana
后綴[4] na
后綴[5] nana

最終的比較結果是 后綴[1] 和 后綴[2] 之間存在最長公共字串?ana。

后記：
已經多次領教了從后往前尋找算法的優勢，EG BM字符串匹配算法，Sunday算法等。這又是一例！

編程珠璣的最后習題部分給出了另外一個問題，如何找到兩個不同的字符串中的最長連續字串？
編程珠璣同樣利用后綴數組給出了解答，不過答案我看不太明白。

還有一道，如何找到出現次數超過M次的最長連續字串。（M>=2, 當M==2時，就相當于找最長重復字串）
答案是
當M=2時，最長重復字串問題，我們使用的函數是 comlen（a[i], a[i+1]）;
當M>2時，我們就需要使用 comlen（a[i], a[i+M-1]）;
eg M=3時， 仍按照上面的例子，求出的最長字串為 “a“,長度為1; 因為a[i] 和 a[i+M-1]的最長重復字串肯定在a[i+1]~a[i+M-2]之間也重復了，也就是至少重復了M次。
本例中 a[0] 和 a[2]的重復字串 “a” 在a[1]中也重復了。
后綴[0]?a
后綴[1] ana
后綴[2]?anana
后綴[3] banana
后綴[4] na
后綴[5] nana

總結

以上是生活随笔為你收集整理的查找一段文字中最长的重复字串 – 编程珠玑（排过序的后缀数组的应用）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。