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

解题思路
给出一种动态规划的解决方案；抽象成两个一样的字符串，求两个字符串的最长公共字串，但是字串的起点不能是一样的。
代码如下：

class Solution {
public:
    int longestRepeatingSubstring(string s) {
        int n = s.size();
        vector<vector<int>>dp(n + 1, vector<int>(n + 1, 0));
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (s[i - 1] == s[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = max(dp[i][j], res);
                }
            }
        }
        return res;
    }
    //抽象成最长公共字串，切记i ！= j
};