猿创征文| 动规了解

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

题目传送门

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" 的子字符串。
1
2
3
4
5
6

思路

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

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

目标串：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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

这个的复杂度时间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());
    }
};
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

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