LeetCode 466题 “Count The Repetitions” 是一个中等难度的字符串问题。题目要求我们计算一个字符串在另一个字符串中的重复次数。具体来说，给定两个字符串 s1 和 s2，我们需要确定 s1 在 s2 中重复的最多次数。

题目描述

定义两个字符串 s1 和 s2，请编写一个函数来计算 s1 在 s2 中重复的最多次数。这里的“重复”是指 s1 可以在 s2 中连续出现多次，并且每次出现的位置可以重叠。

示例

示例 1:

输入: s1 = "ab", s2 = "abab" 输出: 2 解释: "ab" 在 "s2" 中重复了两次。

示例 2:

输入: s1 = "abc", s2 = "abababc" 输出: 1 解释: "abc" 在 "s2" 中重复了一次。

解题思路

1. 暴力解法：
   • 使用双指针分别遍历 s1 和 s2。
   • 每次在 s2 中找到 s1 的一个匹配，记录匹配的次数。
   • 这种方法的时间复杂度为 O(n*m)，其中 n 是 s2 的长度，m 是 s1 的长度。
2. 优化解法：
   • 利用字符串的周期性，找到 s1 在 s2 中的周期性出现模式。
   • 通过计算 s1 和 s2 的最小公倍数来优化匹配过程。
   • 这种方法的时间复杂度可以优化到 O(n + m)。

代码实现

以下是使用优化解法的 Python 代码实现：

def getMaxRepetitions(s1, n1, s2, n2):

index = 0  # s2中的位置
count = 0  # s1重复的次数
recall = {}  # 记录出现过的(s1中的位置, s2中的位置, s1重复的次数)

while True:
    # 遍历s1
    for i in range(len(s1)):
        if s1[i] == s2[index]:
            index += 1
            if index == len(s2):
                index = 0
                count += 1

    # 检查是否已经记录过当前状态
    if (index, count) in recall:
        (prev_index, prev_count) = recall[(index, count)]
        # 计算循环的长度
        circle_len = i - prev_index
        circle_count = count - prev_count
        # 计算总共可以包含多少个循环
        total_count = (n1 - prev_index - 1) // circle_len * circle_count
        # 计算剩余部分
        left_index = prev_index + (n1 - prev_index - 1) % circle_len
        left_count = recall.get((left_index, count), (0, 0))[1]
        return (total_count + left_count) // n2
    else:
        recall[(index, count)] = (i, count)

return count // n2

s1 = "ab" n1 = 1 s2 = "abab" n2 = 1 print(getMaxRepetitions(s1, n1, s2, n2)) # 输出: 2

解释

1. 初始化：
   • index 表示当前在 s2 中的位置。
   • count 表示 s1 在 s2 中重复的次数。
   • recall 是一个字典，用于记录出现过的状态 (index, count) 对应的 (i, count)。
2. 遍历 s1：
   • 对于 s1 中的每个字符，检查是否与 s2 中的当前字符匹配。
   • 如果匹配，更新 index 和 count。
3. 检查循环：
   • 如果当前状态 (index, count) 已经在 recall 中出现过，说明找到了一个循环。
   • 计算循环的长度和循环内的重复次数。
   • 根据循环计算总的重复次数。
4. 返回结果：
   • 计算并返回最终的重复次数。

这个优化解法通过记录状态和检测循环，避免了重复的计算，从而提高了效率。希望这个解释和代码对你理解这道题目有所帮助！