题目描述
给你一个字符串 sequence
,如果字符串 word
连续重复 k
次形成的字符串是 sequence
的一个子字符串,那么单词 word
的 重复值为 k
。单词 word
的 最大重复值 是单词 word
在 sequence
中最大的重复值。如果word
不是 sequence
的子串,那么重复值 k
为 0
。
给你一个字符串 sequence
和 word
,请你返回 最大重复值 k
。
样例
示例1
输入:sequence = "ababc", word = "ab"
输出:2
解释:"abab" 是 "ababc" 的子字符串。
示例2
输入:sequence = "ababc", word = "ba"
输出:1
解释:"ba" 是 "ababc" 的子字符串,但 "baba" 不是 "ababc" 的子字符串。
示例3
输入:sequence = "ababc", word = "ac"
输出:0
解释:"ac" 不是 "ababc" 的子字符串。
提示
1 <= sequence.length <= 100
1 <= word.length <= 100
sequence
和word
都只包含小写英文字母。
算法1
(暴力枚举) $O(n^2)$
- 令
t
=b
; - 如果
a
中可以找到t
,那么让t = t + b
- 一直到找不到
t
为止,t
的延伸次数b
即为答案。
时间复杂度
- 令
n = sequence.size(), m = word.size()
t
最多拓展n/m
次, 每次判断需要$O(n* m * k)$,k
是延伸次数- 故总时间复杂度为 $O(n^3/m)$
C++ 代码
class Solution {
public:
int maxRepeating(string sequence, string word) {
int ans = 1;
string t = word;
while(sequence.find(t) != -1) {
ans ++;
t += word;
}
return ans - 1;
}
};
算法2
(KMP) $O(n)$
- 对此题进行
KMP
扩展以可以解决n = 10^7
级别的问题 - 预处理
kmp
的next
数组,在sequence
中找到word
的所有出现位置 - 找到出现位置中的最长连续递增位置,比如当m=5时,如果在
0,5,10,15
均找到了,那么次数的连续包含长度就是4
. - 可以使用哈希表,记录匹配成功的位置以及对应连续长度。
时间复杂度
- 预处理 next数组需要 $O(m)$的时间
- KMP匹配需要 $O(m + n)$的时间
- 每次匹配成功后更新答案需要$O(1)$的时间
- 由于当
m
<n
时直接返回0
, 因此总有m < n
故总时间复杂度为$O(n)$
C++ 代码
int ne[110];
class Solution {
public:
int maxRepeating(string sequence, string word) {
int n = sequence.size(), m = word.size();
if(m > n) return 0;
ne[0] = -1;
for(int i = 1, j = -1; i < m; i++){
while(j != -1 && word[i] != word[j + 1]) j = ne[j];
if(word[j + 1] == word[i]) j++;
ne[i] = j;
}
unordered_map<int ,int> hash;
int ans = 0;
int last = -1, lastLen = 0;
for(int i = 0, j =-1; i < n; i++){
while(j != -1 && sequence[i] != word[j + 1]) j = ne[j];
if (sequence[i] == word[j + 1])j ++;
if(j + 1 == m){
if(hash.count(i - m + 1 - m)){
int len = hash[i - m + 1] = hash[i - m + 1 - m] + 1;
ans = max(ans, len);
}else{
ans = max(ans, 1);
hash[i - m + 1] = 1;
}
j = ne[j];
}
}
return ans;
}
};
算法3
(KMP) $O(n)$
另一种kmp
的写法是通过补齐p
的长度到可能的最大可能长度, 通过前缀匹配找到答案.
可以参考
@WZC的题解