1668-最大重复子字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

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

给你一个字符串 sequence 和 word ，请你返回 **最大重复值k **。

示例 1：

**输入：** sequence = "ababc", word = "ab"
**输出：** 2
**解释：** "abab" 是 " **abab** c" 的子字符串。

示例 2：

**输入：** sequence = "ababc", word = "ba"
**输出：** 1
**解释：** "ba" 是 "a **ba** bc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。

示例 3：

**输入：** sequence = "ababc", word = "ac"
**输出：** 0
**解释：** "ac" 不是 "ababc" 的子字符串。

提示：

  • 1 <= sequence.length <= 100
  • 1 <= word.length <= 100
  • sequence 和 word 都只包含小写英文字母。

方法一：简单枚举 + 动态规划

思路与算法

我们可以将给定字符串 sequence 的每一个位置作为结束位置，判断前面的若干个字符是否恰好是字符串 word。如果第 i 个位置是，那么可以记录 valid}[i] 的值为 1，否则为 0。

当我们得到了数组 valid 后，就可以计算最大重复值了。我们可以得到递推式：

f[i] = \begin{cases}
f[i-|\textit{word}|] + 1, & \textit{valid}[i]=1 \wedge i \geq |\textit{word}| \
1, & \textit{valid}[i]=1 \wedge i < |\textit{word}| \
0, & \text{otherwise}
\end{cases}

这里 f[i] 表示字符串 word 在第 i 个位置最后一次出现时的最大重复值，那么只有在 valid}[i] 为 1 时最大重复值才不为 0，需要进行递推。字符串 word 在第 i 个位置前出现的最大重复值可以通过 f[i-|\textit{word}|] 获得（其中 |\textit{word}| 表示字符串 word 的长度），如果该项没有意义，那么它的值为 0。

最终的答案即为数组 f 中的最大值。注意到在求解 f[i] 时，我们无需存储除了 valid}[i] 以外的数组 valid 的项。因此可以省去数组 valid。

代码

[sol1-C++]
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
class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int n = sequence.size(), m = word.size();
        if (n < m) {
            return 0;
        }

        vector<int> f(n);
        for (int i = m - 1; i < n; ++i) {
            bool valid = true;
            for (int j = 0; j < m; ++j) {
                if (sequence[i - m + j + 1] != word[j]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                f[i] = (i == m - 1 ? 0 : f[i - m]) + 1;
            }
        }
        
        return *max_element(f.begin(), f.end());
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxRepeating(String sequence, String word) {
        int n = sequence.length(), m = word.length();
        if (n < m) {
            return 0;
        }

        int[] f = new int[n];
        for (int i = m - 1; i < n; ++i) {
            boolean valid = true;
            for (int j = 0; j < m; ++j) {
                if (sequence.charAt(i - m + j + 1) != word.charAt(j)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                f[i] = (i == m - 1 ? 0 : f[i - m]) + 1;
            }
        }

        return Arrays.stream(f).max().getAsInt();
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int MaxRepeating(string sequence, string word) {
        int n = sequence.Length, m = word.Length;
        if (n < m) {
            return 0;
        }

        int[] f = new int[n];
        for (int i = m - 1; i < n; ++i) {
            bool valid = true;
            for (int j = 0; j < m; ++j) {
                if (sequence[i - m + j + 1] != word[j]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                f[i] = (i == m - 1 ? 0 : f[i - m]) + 1;
            }
        }

        return f.Max();
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        n, m = len(sequence), len(word)
        if n < m:
            return 0
        
        f = [0] * n
        for i in range(m - 1, n):
            valid = True
            for j in range(m):
                if sequence[i - m + j + 1] != word[j]:
                    valid = False
                    break
            if valid:
                f[i] = (0 if i == m - 1 else f[i - m]) + 1
        
        return max(f)
[sol1-C]
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
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int maxRepeating(char * sequence, char * word){
    int n = strlen(sequence), m = strlen(word);
    if (n < m) {
        return 0;
    }

    int f[n];
    memset(f, 0, sizeof(f));
    for (int i = m - 1; i < n; ++i) {
        bool valid = true;
        for (int j = 0; j < m; ++j) {
            if (sequence[i - m + j + 1] != word[j]) {
                valid = false;
                break;
            }
        }
        if (valid) {
            f[i] = (i == m - 1 ? 0 : f[i - m]) + 1;
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = MAX(res, f[i]);
    }
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var maxRepeating = function(sequence, word) {
    const n = sequence.length, m = word.length;
    if (n < m) {
        return 0;
    }

    const f = new Array(n).fill(0);
    for (let i = m - 1; i < n; ++i) {
        let valid = true;
        for (let j = 0; j < m; ++j) {
            if (sequence[i - m + j + 1] !== word[j]) {
                valid = false;
                break;
            }
        }
        if (valid) {
            f[i] = (i === m - 1 ? 0 : f[i - m]) + 1;
        }
    }

    return _.max(f);
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxRepeating(sequence, word string) (ans int) {
    n, m := len(sequence), len(word)
    if n < m {
        return
    }
    f := make([]int, n)
    for i := m - 1; i < n; i++ {
        if sequence[i-m+1:i+1] == word {
            if i == m-1 {
                f[i] = 1
            } else {
                f[i] = f[i-m] + 1
            }
            if f[i] > ans {
                ans = f[i]
            }
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(mn)，其中 n 和 m 分别是字符串 sequence 和 word 的长度。

  • 空间复杂度：O(n)，即为数组 f 需要使用的空间。

方法二：KMP 算法 + 动态规划

思路与算法

方法一的数组 valid 本质上就是标记了字符串 word 在字符串 sequence 中所有出现的位置。而我们可以使用更高效的 KMP 算法 在 O(m+n) 的时间内得到数组 valid。对于 KMP 算法本身，本篇题解不再赘述，感兴趣的读者可以自行通过链接进行学习。

代码

[sol2-C++]
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.size(), m = word.size();
        if (n < m) {
            return 0;
        }

        vector<int> fail(m, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && word[j + 1] != word[i]) {
                j = fail[j];
            }
            if (word[j + 1] == word[i]) {
                fail[i] = j + 1;
            }
        }

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

        return *max_element(f.begin(), f.end());
    }
};
[sol2-Java]
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();
    }
}
[sol2-C#]
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
38
public 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];
        Array.Fill(fail, -1);
        int j;
        for (int i = 1; i < m; ++i) {
            j = fail[i - 1];
            while (j != -1 && word[j + 1] != word[i]) {
                j = fail[j];
            }
            if (word[j + 1] == word[i]) {
                fail[i] = j + 1;
            }
        }

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

        return f.Max();
    }
}
[sol2-Python3]
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
class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        n, m = len(sequence), len(word)
        if n < m:
            return 0

        fail = [-1] * m
        for i in range(1, m):
            j = fail[i - 1]
            while j != -1 and word[j + 1] != word[i]:
                j = fail[j]
            if word[j + 1] == word[i]:
                fail[i] = j + 1
        
        f = [0] * n
        j = -1
        for i in range(n):
            while j != -1 and word[j + 1] != sequence[i]:
                j = fail[j]
            if word[j + 1] == sequence[i]:
                j += 1
                if j == m - 1:
                    f[i] = (0 if i == m - 1 else f[i - m]) + 1
                    j = fail[j]
        
        return max(f)
[sol2-C]
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
38
39
40
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int maxRepeating(char * sequence, char * word){
    int n = strlen(sequence), m = strlen(word);
    if (n < m) {
        return 0;
    }

    int fail[m];
    memset(fail, -1, sizeof(fail));
    for (int i = 1; i < m; ++i) {
        int j = fail[i - 1];
        while (j != -1 && word[j + 1] != word[i]) {
            j = fail[j];
        }
        if (word[j + 1] == word[i]) {
            fail[i] = j + 1;
        }
    }

    int f[n];
    memset(f, 0, sizeof(f));
    for (int i = 0, j = -1; i < n; ++i) {
        while (j != -1 && word[j + 1] != sequence[i]) {
            j = fail[j];
        }
        if (word[j + 1] == sequence[i]) {
            ++j;
            if (j == m - 1) {
                f[i] = (i >= m ? f[i - m] : 0) + 1;
                j = fail[j];
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = MAX(res, f[i]);
    }
    return res;
}
[sol2-JavaScript]
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
var maxRepeating = function(sequence, word) {
    const n = sequence.length, m = word.length;
    if (n < m) {
        return 0;
    }

    const fail = new Array(n).fill(-1);
    for (let i = 1; i < m; ++i) {
        let j = fail[i - 1];
        while (j !== -1 && word[j + 1] !== word[i]) {
            j = fail[j];
        }
        if (word[j + 1] === word[i]) {
            fail[i] = j + 1;
        }
    }

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

    return _.max(f)
};
[sol2-Golang]
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
38
39
40
41
42
func maxRepeating(sequence, word string) (ans int) {
    n, m := len(sequence), len(word)
    if n < m {
        return
    }
    fail := make([]int, m)
    for i := range fail {
        fail[i] = -1
    }
    for i := 1; i < m; i++ {
        j := fail[i-1]
        for j != -1 && word[j+1] != word[i] {
            j = fail[j]
        }
        if word[j+1] == word[i] {
            fail[i] = j + 1
        }
    }

    f := make([]int, n)
    j := -1
    for i := 0; i < n; i++ {
        for j != -1 && word[j+1] != sequence[i] {
            j = fail[j]
        }
        if word[j+1] == sequence[i] {
            j++
            if j == m-1 {
                if i < m {
                    f[i] = 1
                } else {
                    f[i] = f[i-m] + 1
                }
                if f[i] > ans {
                    ans = f[i]
                }
                j = fail[j]
            }
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(m + n)，其中 n 和 m 分别是字符串 sequence 和 word 的长度。

  • 空间复杂度：O(m + n)，即为 KMP 算法中的数组 fail 以及数组 f 需要使用的空间。

 Comments
On this page
1668-最大重复子字符串