问题

给定字符串 \(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;
    }
}