1668. 最大重复子字符串

Posted on In , Views: Disqus: Reading time ≈ 2 mins.

给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。
给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    // 遍历
    public int maxRepeating(String sequence, String word) {
        char[] seqArray = sequence.toCharArray();
        char[] wordArray = word.toCharArray();

        int result = 0;
        int n = seqArray.length - wordArray.length + 1;
        // 遍历
        for (int i = 0; i < n; i++) {
            int s = i;
            int e = s + wordArray.length;
            int cnt = 0;
            while (e <= seqArray.length) {
                int j = s;
                for (; j < e; j++) {
                    if (seqArray[j] != wordArray[j - s]) break;
                }
                if (j == e) {
                    cnt++;
                    s = e;
                    e += wordArray.length;
                } else {
                    break;
                }
            }
            if (cnt > result) result = cnt;
        }
        return result;
    }
}

image.png

简单枚举 + 动态规划

image.png

KMP 算法 + 动态规划

方法一的数组 valid 本质上就是标记了字符串 word 在字符串 sequence 中所有出现的位置。而我们可以使用更高效的 KMP 算法 在 O (m+n) O (m+n) 的时间内得到数组 valid。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int maxRepeating(String sequence, String word) {
        int n = sequence.length(), m = word.length();
        if (n < m) {
            return 0;
        }

        int[] fail = new int[m];
        Arrays.fill(fail, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && word.charAt(j + 1) != word.charAt(i)) {
                j = fail[j];
            }
            if (word.charAt(j + 1) == word.charAt(i)) {
                fail[i] = j + 1;
            }
        }

        int[] f = new int[n];
        int j = -1;
        for (int i = 0; i < n; ++i) {
            while (j != -1 && word.charAt(j + 1) != sequence.charAt(i)) {
                j = fail[j];
            }
            if (word.charAt(j + 1) == sequence.charAt(i)) {
                ++j;
                if (j == m - 1) {
                    f[i] = (i >= m ? f[i - m] : 0) + 1;
                    j = fail[j];
                }
            }
        }

        return Arrays.stream(f).max().getAsInt();
    }
}

复杂度分析

  • 时间复杂度：O (m + n) O (m+n)，其中 nn 和 mm 分别是字符串 sequence 和 word 的长度。
  • 空间复杂度：O (m + n) O (m+n)，即为 KMP 算法中的数组 fail 以及数组 f 需要使用的空间。

【字符串哈希】字符串哈希入门
image.png