第十二天最大重复子字符串

最大重复子字符串

问题描述：
给你一个字符串 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” 的子字符串。

问题求解：

class Solution {
    public int maxRepeating(String sequence, String word) {
        int count=0;
        String tmp=word;
        while(sequence.contains(word)){
            word+=tmp;
            count++;
        }
        return count;
    }
}

问题总结：
老规矩我们先看一下官方求解。
方法一：简单枚举 + 动态规划
思路与算法

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

当我们得到了数组 \textit{valid}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]=
⎩
⎪
⎪
⎨
⎪
⎪
⎧
​

f[i−∣word∣]+1,
1,
0,
​

valid[i]=1∧i≥∣word∣
valid[i]=1∧i<∣word∣
otherwise
​

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

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

方法二：KMP 算法 + 动态规划
思路与算法

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

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/maximum-repeating-substring/solution/zui-da-zhong-fu-zi-zi-fu-chuan-by-leetco-r4cp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。