最大重复子字符串

难度: 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 都只包含小写英文字母。

Submission

运行时间: 21 ms

内存: 16.1 MB

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        s = word
        res = 0
        while True:
            if word in sequence:
                res += 1
                word += s
            else:
                break
        return res

Explain

该题解采用了简单直观的方法来解决问题。首先定义两个变量，s用于存储原始的word，res用于记录word重复的次数。通过一个循环，每次循环将word与s进行拼接以形成更长的字符串，并检查这个新形成的字符串是否为sequence的子字符串。如果是，res增加1；如果不是，则终止循环。最终返回的res即为最大重复值k。

时间复杂度: O(n^2/m)

空间复杂度: O(n)

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        s = word  # s存储原始的word
        res = 0  # res用于统计重复的最大次数
        while True:
            if word in sequence:  # 检查当前word是否为sequence的子串
                res += 1  # 如果是，则增加计数
                word += s  # 并将word与s进行拼接形成更长的重复字符串
            else:
                break  # 如果当前word不是子串，结束循环
        return res  # 返回最大重复次数

Explore

这种选择是为了确保每次拼接前，`word`已经是`sequence`的子字符串，从而确保每次拼接后的字符串（如果仍然是子字符串）确实代表了一个有效的重复。如果先进行拼接再检查，可能会造成在`word`尚未成为`sequence`的子字符串时就已经进行了拼接，这将导致不必要的计算和可能的错误结果，因为拼接后的字符串可能根本不是子字符串，从而导致错误地增加重复次数。

在题解中，没有直接的检查来确保`word+s`的长度不会超过`sequence`的长度。这确实可能导致性能损耗，尤其是在`sequence`较短而`word`较长的情况下。一个改进方法是在每次拼接前检查新的`word`长度是否会超过`sequence`的长度。如果超过，则可以提前终止循环。这样可以减少不必要的字符串比较操作，从而优化性能。

这种方法在`word`长度相对于`sequence`非常短，并且`word`可以重复很多次的情况下最不有效。因为每次拼接和检查都涉及到整个`sequence`的遍历，当需要多次重复拼接时，这种方法的效率极低。此外，如果`word`是`sequence`的一个非常频繁重复的子串，但每次都只增加一个`word`长度，这将导致大量的重复检查和字符串操作。在这种情况下，更高效的算法可能是使用KMP算法或其他字符串匹配算法来更快地确定子字符串的位置和重复次数。