1062.md

1062. 最长重复子串

题目：给定一个字符串s，找出最长的重复子串的长度。如果不存在重复的子字符串则返回0.

例1：

输入："adcd"
输出：0
说明：没有重复的子串

例2：

输入："abbaba"
输出：2
说明：最长的重复子串是"ab"和"ba"，每个子串都出现两次。

例3：

输入："aabcaabdaab"
输出：3 
说明：最长的重复子串是"aab"，发生3次数。

例4：

输入："aaaaa"
输出：4
说明：最长的重复子串是"aaaa"，它出现两次。

解

动态规划，两重循环，如果当前位匹配上了，就把前一位DP记录下来的结果 + 1 赋给当前位DP。

class Solution {
    public int longestRepeatingSubstring(String S) {
        if(S == null || S.length() == 0){
            return 0;
        }
        
        int n = S.length();
        int res = 0;
        
        int [][] dp = new int[n+1][n+1];
        for(int i = 1; i<=n; i++){
            for(int j = 1; j<i; j++){
                if(S.charAt(i-1) == S.charAt(j-1)){
                    // 对重复子串的长度进行累加
                    dp[i][j] = dp[i-1][j-1]+1;
                    res = Math.max(res, dp[i][j]);            
                }
            }
        }
        
        return res;
    }
}

解析

以“aabcaabdaab”为例

       a, a, b, c, a, a, b, d, a, a, b
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
a [0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
a [0, 1,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b [0, 0, 0,  0, 0, 0, 0, 0, 0, 0, 0, 0]
c [0, 0, 0, 0,  0, 0, 0, 0, 0, 0, 0, 0]
a [0, 1, 1, 0, 0,  0, 0, 0, 0, 0, 0, 0]
a [0, 1, 2, 0, 0, 1,  0, 0, 0, 0, 0, 0]
b [0, 0, 0, 3, 0, 0, 0,  0, 0, 0, 0, 0]
d [0, 0, 0, 0, 0, 0, 0, 0,  0, 0, 0, 0]
a [0, 1, 1, 0, 0, 1, 1, 0, 0,  0, 0, 0]
a [0, 1, 2, 0, 0, 1, 2, 0, 0, 1,  0, 0]
b [0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0,  0]

二位数组，数据重叠示意图，因为循环限值了j < i，所以右上角是未使用部分，以空格分开，真实使用空间如下：

      a, a, b, c, a, a, b, d, a, a, b
a [0,
a [0, 1,
b [0, 0, 0,
c [0, 0, 0, 0,
a [0, 1, 1, 0, 0,
a [0, 1, 2, 0, 0, 1,
b [0, 0, 0, 3, 0, 0, 0,
d [0, 0, 0, 0, 0, 0, 0, 0,
a [0, 1, 1, 0, 0, 1, 1, 0, 0,
a [0, 1, 2, 0, 0, 1, 2, 0, 0, 1,
b [0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0,

dp[i][j] = dp[i-1][j-1]+1使得重复子串的长度进行累加。

同理，以“aaaaa”为例：

      a, a, a, a, a
  [0, 0, 0, 0, 0, 0]
a [0, 0, 0, 0, 0, 0]
a [0, 1, 0, 0, 0, 0]
a [0, 1, 2, 0, 0, 0]
a [0, 1, 2, 3, 0, 0]
a [0, 1, 2, 3, 4, 0]