LC.P1668[最大重复子字符串]

方法一：暴力枚举

1
2
3
4
5
6
7
8
class Solution {
    public int maxRepeating(String sequence, String word) {
        for (int k = sequence.length() / word.length(); k >= 0; --k) {
            if (sequence.contains(word.repeat(k))) return k;
        }
        return 0;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxRepeating(String sequence, String word) {
        int n = sequence.length(), m = word.length(), ans = 0;
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            if (i - m < 0) continue;
            if (sequence.substring(i - m, i).equals(word)) {
                f[i] = f[i - m] + 1;
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n \times m)$
  • 空间复杂度：$O(n)$