给定一个字符串，求出其最长的重复子串的长度

爱被打了一巴掌 2022-07-15 05:56 236阅读 0赞

题目来源：这是编程珠玑上的一道题目

# 概念 #

## 字符串的前缀和后缀 ##

例如字符串 s =“abcdeabc”  
则s的前缀：  
“a”，“ab”，“abc”，“abcd”，“abcde”，“abcdea”，“abcdeab”，“abcdeabc”其中除了**s字符串本身（“abcdeabc”）**之外，其他的前缀为s的真前缀。

s的后缀：  
“abcdeabc”,“bcdeabc”，“cdeabc”，“deabc”，“eabc”，”abc”,“bc”，“c”其中除了s字符串本身，其他前缀为s的真后缀。

注：这里前缀和后缀中不包括空字符串

## 为什么用后缀 ##

对于字符串s，它所有可能的子串为:  
![这里写图片描述][20161105111728783]  
其中，1，2，3，4， 5， 6，7，8标识的是字符串s的后缀。

通过观察可知：

*  后缀字符串的前缀已经包含了字符串s的部分子串（例如：abcdeabc 的前缀有  
    a，ab，abc，abcd，abcde，abcdea，abcdeab；由图上可知字符串s的子串也包括abcdeabc的前缀）；
 *  因此可知，只需要求出字符串s的所有后缀就可间接的表示了s所有的子串；（因为我们的目的就是求出s所有子串中最长的重复子串的长度）
 *  那么，可以通过比较字符串的s的后缀中相同的前缀就可以求出s中最长的重复子串。

# 解题思路 #

1.  保存s字符串的所有后缀
2.  对所有后缀进行排序（自然排序）
3.  比较排序后的相邻的后缀的最长公共子串（两个后缀从第一个字符开始的就相等得到公共子串），求出最长的公共子串

# 代码 #

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    size_t getCommLen(string str1, string str2) {
        size_t i;
        for (i = 0; i < str1.size() && i < str2.size(); i++) {
            if (str1[i] != str2[i])
                break;
        }
        return i;
    }
    int main()
    {
        string str;
        cin >> str;
        vector<string> strs;
        for (size_t i = 0; i < str.size(); i++) {
            strs.push_back(str.substr(i));
        }
        sort(strs.begin(), strs.end());
    
        size_t maxLen = 0;
        for (size_t i = 0; i < strs.size()-1; i++) {
            size_t len = getCommLen(strs[i], strs[i+1]);
            maxLen = max(maxLen, len);
        }
        cout << maxLen << endl;
        return 0;
    }

# 问题 #

对于字符串s = “abcdefabcdefabc”求出的最长重复子串的长度为 9。  
注意后缀字符串：”abcdefabc”和“abcdefabcdefabc”，很明显这两字符串中有重叠的部分。

所以这个算法并不适用所有的字符串。

# 时空复杂度 #

空间复杂度：求长度为n的字符串的后缀，需要O(n)的空间复杂度  
时间复杂度：sort调用排序的时间复杂度为O(nlogn)，其他的操作都为O(n)，因此该算法的时间复杂度为O(nlogn)。

# 参考题目 #

[后缀数组一·重复旋律][Link 1]  
[后缀数组二·重复旋律2][2]  
[后缀数组三·重复旋律3][3]

[20161105111728783]: /images/20220715/3104e0981c6e47648c0a48908147bf65.png
[Link 1]: http://hihocoder.com/problemset/problem/1403
[2]: http://hihocoder.com/problemset/problem/1407
[3]: http://hihocoder.com/problemset/problem/1415