一、题目描述
题目：重复叠加字符串匹配
难度：中等
描述：给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
注意：字符串 “abc” 重复叠加 0 次是 “”，重复叠加 1 次是 “abc”，重复叠加 2 次是 “abcabc”。
示例1
输入：a = “abcd”, b = “cdabcdab”
输出：3
解释：a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。
示例2
输入：a = “a”, b = “aa”
输出：2
示例3
输入：a = “abc”, b = “wxyz”
输出：-1
二、题目解析
本题并不需要用到多么高深的算法，题中的中心思想在于对多个a字符串进行叠加，由此不难想到如果想要满足所有情况至少需要叠加多少个a，找到这个数量之后每次构建出最长的备选字符串new_str，从左到右遍历new_str在字符串new_str中找到了字符串b之后统计剩余子串中有多少个完整的字符串a，减去其个数即可。
构建最长的字符串new_str
考虑如下的情况不难得到当new_str的长度为len(b)//len(a)+2的时候可以满足任何情况（a的长度大于b时另作考虑）
当构建好了new_str时，new_str中包含没用到的字符串a时的情形如下：
三、解题代码
解法（一）
按照解析中的方法进行代码编写如下：
class Solution: def repeatedStringMatch(self, a: str, b: str) -> int: # 得到满足任何条件的最小叠加字符串new_str # 如果a可以作为子串，此时的new_str中一定含有正确答案 res = len(b) // len(a) if len(b) // len(a) != 0 else 1 new_str = a * (res + 2) for i in range(len(new_str) - len(b) + 1): if new_str[i] == b[0]: # 当能在new_str中找到b时进行判断 if new_str[i:i + len(b)] == b: # 从后面看，剩余长度超过2*len(a)的情况 if len(new_str) - i - len(b) >= 2 * len(a): return res # 长度超过len(a)的情况 elif len(new_str) - i - len(b) >= len(a): return res + 1 else: return res + 2 return -1
解法（二）
直接使用Python中的字符串判断（a in b）方法进行编写：
class Solution: def repeatedStringMatch(self, a: str, b: str) -> int: min = len(b) // len(a) for i in range(min, min + 3): if b in a * i: return i return -1
