1.题目基本信息

1.1.题目描述

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。

• 例如，str == ["abc", 3] =="abcabcabc" 。

如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。

• 例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，仅需要删除加粗且用斜体标识的字符。

现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。

请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。

1.2.题目地址

https://leetcode.cn/problems/count-the-repetitions/description/

2.解题方法

2.1.解题思路

找循环节。题目转换为[s1,n1]中s2的序列个数totalS2cnt，题解=totalS2cnt//n2

2.2.解题步骤

第一步，找循环节。构建维护变量。index维护s2最后匹配字符的索引；s1cnt维护当前用掉的s1的个数；s2cnt维护当前匹配到的s2的个数；map1维护s1遍历完时的index->(s1使用个数,s2匹配个数)的映射；loopS1cnt和loopS2cnt维护每个循环节消耗s1的个数和匹配的s2的个数

• 1.1.遍历当前消耗的s1，更新维护变量

• 1.2.所有s1消耗完还没有找到循环节的情况

• 1.3.当前s1遍历完成后的index在哈希表中，代表找到了循环节；保存循环节的信息并退出循环，前s1cnt1个s1中包含s2cnt1个s2串，后续的循环节中每loopS1cnt个s1串中含有loopS2cnt个s2子串

  • 1.3.1.将循环节前面部分匹配的s2加入到答案中

• 1.4.没有找到循环节，更新维护变量map1

第二步，计算循环节中的s2的个数

第三步，将循环节后面的部分进行暴力匹配

3.解题代码

python代码

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        # 思路：找循环节。题目转换为[s1,n1]中s2的序列个数totalS2cnt，题解=totalS2cnt//n2
        if n1 == 0:
            return 0
        # 第一步，找循环节。构建维护变量。index维护s2最后匹配字符的索引；s1cnt维护当前用掉的s1的个数；s2cnt维护当前匹配到的s2的个数；map1维护s1遍历完时的index->(s1使用个数,s2匹配个数)的映射；loopS1cnt和loopS2cnt维护每个循环节消耗s1的个数和匹配的s2的个数
        totalS2cnt = 0
        index, s1cnt, s2cnt = 0, 0, 0
        loopS1cnt, loopS2cnt = None, None
        map1 = {}
        while True:
            # 1.1.遍历当前消耗的s1，更新维护变量
            s1cnt += 1
            for c in s1:
                if c == s2[index]:
                    index += 1
                    if index == len(s2):
                        index = 0
                        s2cnt += 1
            # 1.2.所有s1消耗完还没有找到循环节的情况
            if s1cnt == n1:
                return s2cnt // n2
            if index in map1:
                # 1.3.当前s1遍历完成后的index在哈希表中，代表找到了循环节；保存循环节的信息并退出循环，前s1cnt1个s1中包含s2cnt1个s2串，后续的循环节中每loopS1cnt个s1串中含有loopS2cnt个s2子串
                s1cnt1, s2cnt1 = map1[index]
                loopS1cnt, loopS2cnt = s1cnt - s1cnt1, s2cnt - s2cnt1
                # 1.3.1.将循环节前面部分匹配的s2加入到答案中
                totalS2cnt += s2cnt1
                break
            else:
                # 1.4.没有找到循环节，更新维护变量map1
                map1[index] = (s1cnt, s2cnt)
        # 第二步，计算循环节中的s2的个数
        totalS2cnt +=  (n1 - s1cnt1) // loopS1cnt * loopS2cnt
        # 第三步，将循环节后面的部分进行暴力匹配
        restS1cnt = (n1 - s1cnt1) % loopS1cnt
        for i in range(restS1cnt):
            for c in s1:
                if c == s2[index]:
                    index += 1
                    if index == len(s2):
                        index = 0
                        totalS2cnt += 1
        return totalS2cnt // n2

4.执行结果