【2022-11-03每日一题】1668. 最大重复子字符串[Easy]

2022-11-03每日一题：1668. 最大重复子字符串

难度：Easy

标签：字符串 、 字符串匹配

给你一个字符串 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 都只包含小写英文字母。

方法一：简单枚举 + 动态规划

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func maxRepeating(sequence string, word string) int {
    m, n, ans := len(word), len(sequence), 0
    if m > n { // word 长度大于 sequence， 直接返回
        return ans
    }
    f := make([]int, n)
    for i := m - 1; i < n; i++ {
        if sequence[i-m+1:i+1] == word {
            if i == m - 1 { // 首次
                f[i] = 1
            } else {
                f[i] = f[i-m] + 1
            }
            if f[i] > ans {
                ans = f[i]
            }
        }
    }
	return ans
}

复杂度分析

• 时间复杂度：O(mn)，其中 n 和 m 分别是字符串 sequence 和 word 的长度。
• 空间复杂度：O(n)，即为数组 f 需要使用的空间。

方法二：直接枚举

func maxRepeating(sequence string, word string) int {
    for k := len(sequence)/len(word); k > 0; k-- {
        // strings.Repeat(word, k) 拼接 k 个 word 然后判断是否是 sequence 子串
        if strings.Contains(sequence, strings.Repeat(word, k)) {
            return k
        }
    }
    return 0
}

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串 sequence 的长度。
• 空间复杂度：O(n)，即为数组 f 需要使用的空间。

方法三：KMP 算法 + 动态规划

• KMP 算法

func maxRepeating(sequence, word string) int {
    m, n, ans := len(word), len(sequence), 0
    if n < m { // word 长度大于 sequence， 直接返回
        return ans
    }
    // 初始化 kmp
    fail := make([]int, m)
    for i := range fail {
        fail[i] = -1
    }
    for i := 1; i < m; i++ {
        j := fail[i-1]
        for j != -1 && word[j+1] != word[i] {
            j = fail[j]
        }
        if word[j+1] == word[i] {
            fail[i] = j + 1
        }
    }

    // 开始处理
    f, j := make([]int, n), -1
    for i := 0; i < n; i++ {
        for j != -1 && word[j+1] != sequence[i] {
            j = fail[j]
        }
        if word[j+1] == sequence[i] {
            j++
            if j == m-1 {
                if i < m {
                    f[i] = 1
                } else {
                    f[i] = f[i-m] + 1
                }
                if f[i] > ans {
                    ans = f[i]
                }
                j = fail[j]
            }
        }
    }
    return ans
}

复杂度分析

• 时间复杂度：O(m+n)，其中 n 和 m 分别是字符串 sequence 和 word 的长度。

  空间复杂度：O(m+n)，即为 KMP 算法中的数组 fail 以及数组 f 需要使用的空间。

LeetCode题库地址

• https://leetcode.cn/problems/maximum-repeating-substring