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;
    }
}