题解 | #最长重复子串#

思路：

题目的主要信息：

• 重复字符串是由两个相同的字符串首尾拼接而成，不存在覆盖
• 返回的是字串长度，为重复部分的2倍，必为偶数
• 若不存在任何重复字符子串，则返回0

方法一：暴力解法（超时）
具体做法：
n记录最长的重复字串的重复长度，从字符串长度一半开始，然后依次比较后面的n个字符及再后面的n个字符是否相等，若是相等返回即可，若是不等则需要将n减一，相当于缩短重复字串长度继续。

class Solution {
public:
    int solve(string a) {
        int n = a.length() / 2;   //记录最长的重复字串的重复长度，从字符串长度一半开始
        bool flag = true; //记录是否出现过不相等
        for(int i = n; i > 0; i--)
            for(int j = 0; j <= a.length() - i - 1; j++){
                for(int k = j; k < j + n; k++){
                    if(a[k] != a[k + i])
                        flag = false;
                }
                if(flag) //未出现不相等，
                    return 2 * i;
                flag = true;
            }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：，三层循环
• 空间复杂度：，只有临时变量，无额外空间

方法二：二分+字串比较
具体做法：
二分思想，如果存在重复子串的重复部分max的话,,然后逐步递减到0.比较的时候可以不用一个字符一个字符地比较。而是截取max长度，直接比较整串。

class Solution {
public:
    int solve(string a) {
        int max = a.length() / 2;
        while(max > 0){
            int i = 0;
            while(i + max * 2 <= a.length()){
                if(a.substr(i, max) == a.substr(i + max, max)) //比较相邻max个字串是否相等
                    return max * 2;
                i++;
            }
            max--; //减少最长长度，继续查找
        }
        return max;
    }
};

复杂度分析：

• 时间复杂度：，二分查找，加上比较
• 空间复杂度：，无额外空间