题解 | #最长重复子串#

题目描述
一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。
给定一个字符串，请编写一个函数，返回其最长的重复字符子串。
若不存在任何重复字符子串，则返回0。

方法一：暴力解法

求解思路
对于本题目，我们直到这个重复的子串是小于原字符串的一半的。然后我们对子串进行一一列举，从长度为1的子串一直到长度为原字符串一半长度的子串。继而将列举出来的字符串进行重复判断，即可得到题目的答案。

图片说明

解题代码

class Solution {
public:
    //对具体的起点与长度，确认字符串是否为重复拼接形式
    bool check(string& a, int alen, int begin) 
    {
        for(int i = begin; i < alen + begin; ++i) 
        {
            if(a[i] != a[i + alen]) 
            {   //这说明字符串肯定不存在重复在其后面，返回false
                return false;
            }
        }
        return true; // 返回ture
    }
    int solve(string a) 
    {
        int n = a.length();
        for(int i = n / 2; i > 0; --i) 
        {   //枚举长度
            for(int j = 0; j <= n - i - i; ++j) 
            {   //枚举起点
                if(check(a, i, j)) 
                {
                    return 2 * i; // 找到重复字符串
                }
            }
        }
        return 0; // 否则返回0，结束程序
    }
};

复杂度分析
时间复杂度：使用了三层循环，因此时间复杂度为 $O( )$
空间复杂度：没有引入新的内存地址空间，因此空间复杂度为 $O(1)$

方法二：优化方法

求解思路
对于第一种暴力解法，由于时间复杂度是立方级别，因此方法二对其进行优化。我们对三层循环进行优化，发现当我们对于一个长度为len的子串进行判断时，如果它不是重复子串，那么a[i]和a[i+len]开头的子串的结果是一样的，因此对于一个给定的长度，只需要对字符串进行一次遍历即可，这样使得时间复杂度降低一次方，变成二次方的级别。

图片说明

解题代码

class Solution {
public:
    int solve(string a)
    {
        int n = a.length(), hyres = 0;
        for(int i = n / 2; i > 0; --i)
        {   //枚举长度
            for(int j = 0; j < n - i; ++j)
            {   //枚举起点
                if(a[j] == a[i + j])
                {
                    ++hyres; // 满足判断条件，hyres加一
                }
                else
                {
                    hyres = 0; // 不满足条件则重置长度
                }
                if(hyres == i) return i * 2;
            }
        }
        return 0;
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O( )$
空间复杂度：没有引入新的内存地址空间，因此空间复杂度为 $O(1)$