1062.最长重复子串

问题

给定字符串 $S$，找出最长重复子串的长度。如果不存在重复子串就返回 $0$。 示例 1：

输入：$"abcd"$ 输出：$0$ **解释：**没有重复子串。

示例 2：

输入：$"abbaba"$ 输出：$2$ **解释：**最长的重复子串为 $"ab"$ 和 $"ba"$，每个出现 $2$ 次。

示例 3：

输入：$"aabcaabdaab"$ 输出：$3$ **解释：**最长的重复子串为 $"aab"$，出现 $3$ 次。

示例 4：

输入：$"aaaaa"$ 输出：$4$ **解释：**最长的重复子串为 $"aaaa"$，出现 $2$ 次。  

提示：

• 字符串 $S$ 仅包含从 $a$ 到 $z$ 的小写英文字母。
• $1<=S.length<=1500$

解法1（暴力循环）

$O(n^3)$的解决方案。三层循环，最里面一层判断是否为重复子串。

代码1（暴力循环）

class Solution {
    public int longestRepeatingSubstring(String str) {
        int len = str.length();
        int res = 0;
        // 大循环
        for (int i = 0; i < len; i++) {
            // 控制相同字符串第二串的起始索引，注意是i+1的。
            for (int j = i + 1; j < len; j++) {
                // 本层循环里面的重复字符串长度
                int currLen = 0;
                for (int k = 0; j + k < len; k++) {
                    // 第三个变量向前推进，直到不相等为止
                    if (str.charAt(i + k) == str.charAt(j + k)) {
                        currLen++;
                        //判断长度与保存的长度大小
                        res = Math.max(res, currLen);
                    } else {
                        //不符合直接跳出该层循环
                        break;
                    }
                }
            }
        }
        return res;
    }
}

解法2（动态规划）

设$f(i,j)$为$S[i:i+k]$与$S[j:j+k]$重复字符串的长度，并且$S[i]==S[j]$，那么会有 $f(i,j)=f(i-1,j-1)+1$。 换句话说就是，如果$S[i]==S[j]$，那么$i-1$与$j-1$原有的重复字符串长度需要$+1$。 这一考虑的空间复杂度为$O(N)$，时间复杂度为$O(N^2)$

代码2（动态规划）

class Solution {
    public int longestRepeatingSubstring(String str) {
        int len = str.length();
        char[] chars = str.toCharArray();
        int res = 0;
        //第一层没什么特殊的，直接循环即可，需要注意的一点是跳出条件为len-res，因为当i超过len-res时，已经绝对不可能再出现大于res的结果了。直接跳出即可。
        for (int i = 0; i < len - res; i++) {
            int curr = 0;
            //注意这里j要从i+1开始计算，因为重复字符串肯定不能从相同起始索引比较起
            for (int j = i + 1, k = 0; j < len - res + curr; j++, k++) {
                // 注意这里比较的是k与j,
                if (chars[k] == chars[j]) {
                    curr++;
                    res = Math.max(res, curr);
                } else {
                    curr = 0;
                }
            }
        }
        return res;
    }
}