# 0686. 重复叠加字符串匹配
### 题目地址(686. 重复叠加字符串匹配)
### 题目描述
```
给定两个字符串 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 = "a", b = "a"
输出：1
示例 4：
输入：a = "abc", b = "wxyz"
输出：-1
提示：
1 <= a.length <= 104
1 <= b.length <= 104
a 和 b 由小写英文字母组成
```
### 前置知识
* set
### 公司
* 暂无
### 思路
首先，一个容易发现的点是**如果 b 中包含有 a 中没有的字符， 那么一定需要返回 - 1**。因此使用集合存储 a 和 b 的所有字符，并比较 b 是否是 a 的子集，如果不是，则直接返回 - 1。
接着我们逐个尝试：
* 两个 a 是否可以？
* 三个 a 是否可以？
* 。。。
* n 个 a 是否可以？
如果可以，则直接返回 n 即可。关于是否可以的判断， 我们可以使用任何语言自带的 indexof 算法，Python 中 可以使用 `b in a` 判读 b 时候是 a 的子串。
代码:
```py
cnt = 1
while True:
if b in a * cnt:
return cnt
cnt += 1
return -1
```
上面的代码有 BUG，会在一些情况无限循环。比如：
```
a = "abcabcabcabc"
b = "abac"
```
因此我们必须设计出口，并返回 -1。问题的我们的上界是什么呢？
这里有个概念叫**解空间**。这是一个很重要的概念。 我举个简单的例子。 你要在一个数组 A 中找某一个数的索引，题目保证这个数字一定在数组中存在。那么这道题的解空间就是 **\[0, n -1]**，其中 n 为数组长度。你的解不可能在这个范围外。
回到本题，如果 a 经过 n 次可以匹配成功， 那么最终 a 的长度范围是 \[len(b), 2 \* len(a) + len(b)]。
下界是 len(b) 容易理解， 关键是上界。
假设 a 循环 n 次可以包含 b。那么必定属于以下几种情况中的一种：
> 循环次数下界为 len(b) + len(a ) - 1 / len(a)
1. 循环 n 次正好匹配。 比如 a = 'abc', b = 'abcabcabcabcabc'（5 个 abc）。循环 5 次恰好匹配，这五次循环其实就是上面提到到**下界**
2. 第 n 次循环恰好匹配，这个时候第 n 次循环的前 k 个字符必定匹配（其中 0 < k <= len(a)），比如 a = 'abc', b = 'abcabcab'。第三次匹配正好匹配，且匹配了 abc 中的前两个字符 ab，也就是说比下界**多循环一次**。
3. 再比如： a = "ab", b = "bababa"，那么需要循环 5 次 变成 a**babababa**b（粗体表示匹配 b 的部分），其中 3 次是下界，也就是说比下界多循环了**两次**。
除此之前没有别的可能。
可以看出实际上 n 不会大于**下界次循环 + 2**，因此最终 a 的长度的临界值就是 2 \* len(a) + len(b)。**超过这个范围再多次的叠加也没有意义。**
### 关键点解析
* 答案是有限的， 搞清楚解空间是关键
### 代码
代码支持: Python
```py
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
if not set(b).issubset(set(a)):
return -1
cnt = 1
while len(a * cnt) < 2 * len(a) + len(b):
if b in a * cnt:
return cnt
cnt += 1
return -1
```
**复杂度分析**
* 时间复杂度：b in a 的时间复杂度为 M + N（取决于内部算法），因此总的时间复杂度为 $O((M + N) ^ 2)$，其中 M 和 N 为 a 和 b 的长度。
* 空间复杂度：由于使用了 set，因此空间复杂度为 $O(M +N)$，其中 M 和 N 为 a 和 b 的长度。
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/686.repeated-string-match.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.