打怪之路

• 一道简单题让大家了解动规
• • 题目传送门
  • 题目描述
  • 思路

一道简单题让大家了解动规

题目传送门

1668. 最大重复子字符串 - 力扣（Leetcode）

题目描述

给你一个字符串 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" 的子字符串。

思路

这道题看起来感觉很复杂其实很简单，本身对复杂度没有要求，

解题：需要我们在目标串中去反复找规定的子串，目标串不会变化，子串每找到一次就需要再加一次子串，然后在目标串找新的子串；

目标串：abbababa

子串：ba

第一次需要找ba —》第二次就需要找baba -》》以此类推直到找不到为止

所以就会有动态规划算法出现，子串就像一个窗口，这个窗口每次都会增加一个次子串

这道题不管暴力还是用kmp算法都会使用到动态规划

暴力动规代码

class Solution {
public:int maxRepeating(string sequence, string word) {string ans = word;//子串需要存一个，后面加的是子串不是这个串int k = 0;while(sequence.find(ans)!=string::npos){ans+=word;k++;}return k;}
};

这个的复杂度时间O（mn）空间需要k个word的长度O（kn）

kmp是找字符串重复的最好的算法，可以把时间缩成线性

kmp算法解题(因为kmp我还没有写博客总结这里就把官网的解题扒下来了)

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

kmp算法我会尽快给大家出一个详细的博客来参考学习