原文链接: https://leetcode-cn.com/problems/repeated-string-match

英文原文

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b​​​​​​ to be a substring of a after repeating it, return -1.

Notice: string "abc" repeated 0 times is "",  repeated 1 time is "abc" and repeated 2 times is "abcabc".

 

Example 1:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

Example 2:

Input: a = "a", b = "aa"
Output: 2

Example 3:

Input: a = "a", b = "a"
Output: 1

Example 4:

Input: a = "abc", b = "wxyz"
Output: -1

 

Constraints:

• 1 <= a.length <= 104
• 1 <= b.length <= 104
• a and b consist of lower-case English letters.

中文题目

给定两个字符串 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 由小写英文字母组成

通过代码

官方题解

方法一：

这个问题可以概括为“最小的 k 是什么，B 是 A*k 的子串？”我们可以试试每一个 k。

算法：

• 假设我们写了 S = A+A+A+...,如果 B 是 S 的子串，我们只需要检查一些 S[0:], S[1:], ..., S[len(A) - 1:] 是否以 B 开头，因为 S 的长度足以包含 B。
• 现在，假设 q 是 len(B)<=len(A*q) 的最小数。我们只需要检查 B 是 A*q 的子串还是 A*(q+1) 的子串。如果我们尝试 k<q，那么 B 的长度大于 A*q，因此不能是子字符串。当 k=q+1 时，A*k 已经足够大，可以尝试 B 的所有位置，即 A[i:i+len(B)] == B，i = 0, 1, ..., len(A) - 1。

复杂度分析

• 时间复杂度：$O(N*(N+M))$。其中 $M,N$ 是字符串 A,B 的长度。我们创建了两个字符串 A*q，A*(q+1)，其复杂度最多为 O(M+N)。当检查 B 是否是 A 的子串时，复杂度为 $O(N)$。
• 空间复杂度：如上所述，我们创建了使用 $O(M+N)$ 空间的字符串。

方法二：Rabin-Karp

与方法 1 一样，我们将问题简化为确定 B 是否是某个 A*k 的子串。使用以下方法，我们在 $O(len(A) * k)$ 的时间复杂度可以确定 B 是否是 A 的子串。

算法：

• 对于字符串 $S$，将每个 $S[i]$ 当作 ASCII 码。然后，然后$\mathcal{M}$:
  $$\text{hash}(S) = \sum_{0 \leq i < len(S)} p^i * S[i]$$
• 值得注意的是，$\text{hash}(S[1:] + x) = \frac{(\text{hash}(S) - S[0])}{p} + p^{n-1} x$ 。这表明我们可以得到时间复杂度与每个子串的散列值 A * q 大小成线性关系。（我们还将使用 $p^{-1} = p^{\mathcal{M}-2} \mod \mathcal{M}$ 。）
• 然而，哈希值可能会偶然发生冲突。为了解决冲突，我们应该用通常的方法检查答案。我们进行的检查的预期次数是 $1 + \frac{s}{\mathcal{M}}$。

复杂度分析

• 时间复杂度：$O(M+N)$。其中 $M,N$ 是字符串 A,B 的长度。
• 空间复杂度：$O(1)$。只有整数与附加的内存一起存储。

统计信息

通过次数	提交次数	AC比率
17955	50237	35.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
重复的子字符串	简单