题目描述
给定一个字符串 sequence
,如果字符串 word
连续重复 k
次形成的字符串是 sequence
的一个子字符串,那么单词 word
的 重复值为 k
。单词 word
的 最大重复值 是单词 word
在 sequence
中最大的重复值。如果 word
不是 sequence
的子串,那么重复值 k
为 0
。
给你一个字符串 sequence
和 word
,请你返回 最大重复值 k
。
样例
输入:sequence = "ababc", word = "ab"
输出:2
解释:"abab" 是 "ababc" 的子字符串。
输入:sequence = "ababc", word = "ba"
输出:1
解释:"ba" 是 "ababc" 的子字符串,但 "baba" 不是 "ababc" 的子字符串。
输入:sequence = "ababc", word = "ac"
输出:0
解释:"ac" 不是 "ababc" 的子字符串。
限制
1 <= sequence.length <= 100
1 <= word.length <= 100
sequence
和word
都只包含小写英文字母。
算法
(字符串匹配 / KMP) $O(n)$
- 如果
sequence
的长度小于word
,直接返回 0。 - 将
word
按照自身的循环节将长度补齐到n
,将补齐后的字符串看做模式串pattern
。 - 目标是求出
sequence
与pattern
的某个前缀最大的匹配度。 - 这个问题可以通过 KMP 求解,在匹配过程中,追踪匹配的长度,然后将当前匹配长度除以
m
下取整更新答案。
时间复杂度
- 两个长度为 $n$ 字符串 KMP 算法的时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储临时字符串和
nxt
数组。
C++ 代码
class Solution {
public:
int maxRepeating(string sequence, string word) {
const int n = sequence.size(), m = word.size();
if (n < m)
return 0;
string p(n, ' ');
for (int i = 0; i < m; i++)
p[i] = word[i];
for (int i = m; i < n; i++)
p[i] = p[i - m];
vector<int> nxt(n);
nxt[0] = -1;
for (int i = 1, j = -1; i < n; i++) {
while (j > -1 && p[i] != p[j + 1]) j = nxt[j];
if (p[i] == p[j + 1])
j++;
nxt[i] = j;
}
int ans = 0;
for (int i = 0, j = -1; i < n; i++) {
while (j > -1 && sequence[i] != p[j + 1]) j = nxt[j];
if (sequence[i] == p[j + 1])
j++;
ans = max(ans, (j + 1) / m);
}
return ans;
}
};