企业官网建设流程全解析

LeetCode 686 重复叠加字符串匹配：解空间思维与子串搜索上界推导

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本篇基于 leetcode 题解仓库 problems/686.repeated-string-match.md 展开，完整讲解 LeetCode 686「重复叠加字符串匹配」（Repeated String Match）这道中等难度题。核心价值不在于「暴力叠加试到成功」，而在于用解空间（solution space）思维推导出叠加次数的上界，避免盲目循环导致死循环或超时。读完本文，你将掌握：如何用集合预判无解情形、如何推导重复次数的数学上界2 * len(a) + len(b)、以及如何把朴素子串匹配升级为 KMP / 滚动哈希的线性时间算法。

题目描述与约束

给定两个字符串a和b，寻找重复叠加字符串a的最小次数，使得字符串b成为叠加后的字符串a的子串，如果不存在则返回-1。

注意叠加的定义：字符串"abc"重复叠加 0 次是""，重复叠加 1 次是"abc"，重复叠加 2 次是"abcabc"。

示例

约束条件

• 1 <= a.length <= 10^4
• 1 <= b.length <= 10^4
• a和b由小写英文字母组成

数据规模达到万级，说明我们不能真的无限叠加下去，必须在有限次数内给出确定答案。

前置知识

• set（集合）：用于字符集合的快速子集判断，是本题的第一层剪枝手段。
• 字符串匹配算法：本题的匹配操作b in a依赖语言内置算法，其背后通常是朴素的线性扫描或更快的模式匹配算法。仓库的 thinkings/basic-algorithm.md 中「字符串问题」一节列出了朴素、KMP、RK、BM、trie 等常见字符串匹配技术，本文最后会给出 KMP 与滚动哈希的进阶解法。

思路一：字符集合预判，快速排除无解情形

一个容易观察到的点是：如果b中包含有a中没有的字符，那么无论a叠加多少次，b都不可能是叠加串的子串，因为叠加只会在字符集内重复。

因此第一步使用集合存储a和b的所有字符，并判断b的字符集合是否是a的字符集合的子集：

if not set(b).issubset(set(a)): return -1

这一判断可以在叠加开始前直接排除大量无解用例（例如示例 4：a = "abc",b = "wxyz"，w、x、y、z均不在a中，直接返回 -1），避免无意义的字符串构造。

思路二：逐个尝试叠加次数，及朴素写法的 BUG

排除无解情形后，自然的思路是逐个尝试：

• 两个a是否可以？
• 三个a是否可以？
• ……
• n个a是否可以？

如果可以，直接返回n。关于「是否可以」的判断，可以使用任何语言自带的indexOf算法；Python 中可以用b in a判断b是否是a的子串。第一版直觉代码如下：

cnt = 1 while True: if b in a * cnt: return cnt cnt += 1 return -1

这段代码有 BUG，会在某些情况无限循环。例如：

a = "abcabcabcabc" b = "abac"

b包含字符c，且c在a中出现过，集合预判无法拦截；但"abac"永远不会成为周期串"abc"的子串，于是cnt会一直累加，a * cnt无限膨胀，程序陷入死循环甚至内存溢出。

因此我们必须设计循环出口，并在出口处返回 -1。问题的关键就变成了：叠加次数的上界是多少？

解空间思维：叠加次数的上界推导

「上界」问题对应计算机科学中一个很重要的概念——解空间（solution space）。

举一个简单的例子：要在数组A中找某一个数的索引，题目保证这个数字一定存在。那么这道题的解空间就是[0, n - 1]，其中n为数组长度，你的解不可能落在这个范围外。一旦明确了解空间，穷举就有了边界，算法就有了终止保证。

回到本题：如果a经过n次叠加可以匹配成功，那么最终叠加串a * n的长度范围是[len(b), 2 * len(a) + len(b)]。

• 下界是len(b)：很容易理解——叠加串至少要跟b一样长，才可能包含b。
• 上界是2 * len(a) + len(b)：这是关键。

为了理解上界，先定义下界循环次数为：

⌈(len(b) + len(a) - 1) / len(a)⌉，即用len(b)除以len(a)向上取整（这里用len(a) - 1实现向上取整）。

假设a循环n次可以包含b，那么必定属于以下三种情况之一：

情况 1：循环n次正好匹配（n 恰好等于下界）。例如a = 'abc',b = 'abcabcabcabcabc'（5 个abc）。循环 5 次恰好匹配，这 5 次循环就是上面提到的下界循环次数。

情况 2：第n次循环恰好匹配，且第n次循环的前k个字符参与匹配（0 < k <= len(a)），即比下界多循环一次。例如a = 'abc',b = 'abcabcab'。b长度为 8，下界为⌈(8 + 3 - 1)/3⌉ = ⌈10/3⌉ = 4？让我们直接看匹配：第 3 次循环的"abcabcabc"中，前 8 个字符"abcabcab"正好是b，即第 3 次循环匹配了abc的前两个字符ab——注意a的第 3 次叠加只贡献了"ab"就完成了匹配，也就是说比下界多循环了一次。

情况 3：比下界多循环两次。例如a = "ab",b = "bababa"。需要循环 5 次得到ababababab，其中匹配b的部分是加粗的a**babababa**b，"bababa"恰好被包含在其中。这里下界循环次数为⌈(6 + 2 - 1)/2⌉ = ⌈7/2⌉ = 4，而实际需要 5 次，比下界多循环了两次。

除此之外没有别的可能。为什么最多只多两次？因为叠加串是周期性的：当叠加串长度达到len(b)后，b的匹配起点只能落在a的某一周期内（起点最多偏移一个a的长度），匹配终点最多再延伸一个a的长度，再多叠加只会重复已有周期，不会产生新的匹配机会。

由此得出结论：实际循环次数n不会大于「下界循环次数 + 2」，因此叠加串长度的临界值就是2 * len(a) + len(b)。超过这个范围再多次叠加也没有意义——这就是循环终止的出口。

最终解法：Python 实现与复杂度分析

代码支持：Python

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

代码要点

• 先做字符集合子集判断，拦截无解用例；
• 循环条件用len(a * cnt) < 2 * len(a) + len(b)显式控制上界，确保循环必然终止；
• 每次循环内用 Python 内置的in运算符完成子串匹配，命中即返回当前次数cnt；
• 循环正常退出（叠加串长度达到临界值仍不匹配）则返回 -1。

复杂度分析

• 时间复杂度：b in a的时间复杂度为O(M + N)（取决于语言内部字符串匹配算法的实现），叠加次数最多为O(N / M)量级，因此总的时间复杂度为O((M + N) ^ 2)，其中M和N分别为a和b的长度。
• 空间复杂度：由于使用了set存储字符集合，空间复杂度为O(M + N)，其中M和N为a和b的长度。此外每次循环构造的a * cnt临时串也占用O(N + 2M)级别的空间。

关键点总结

• 答案是有限的，搞清楚解空间是关键。先推导出重复次数的上界，再在有限范围内穷举，是这类「无限操作」题型的通用破题思路。
• 集合预判（set(b).issubset(set(a))）是最廉价的第一层剪枝，能直接排除字符集不兼容的无解输入。
• 朴素写法（while True无出口）在a为周期串、b永远不匹配时会死循环，必须以上界2 * len(a) + len(b)作为终止条件。

进阶优化：从内置匹配到 KMP 与滚动哈希

朴素解法的O((M + N)^2)时间复杂度来源于每次叠加都重新做一次全串子串匹配。仓库的 thinkings/basic-algorithm.md 明确指出字符串问题可用的技术栈包括朴素、KMP、RK、BM、trie 等，下面给出两种把匹配阶段降为线性时间的思路（均以上界构造text = a * k，其中k为上面推导出的下界循环次数 + 2，然后在此窗口内匹配b）。

思路 A：KMP 单次扫描

构造长度不超过2 * len(a) + len(b)的叠加串后，只需调用一次 KMP 匹配，无需逐次叠加、逐次重扫：

1. 先对模式串b预处理出next（前缀函数）数组，复杂度O(N)；
2. 在目标串text = a * k上执行一次 KMP 扫描，复杂度O(len(text)) = O(M + N)；
3. 若在k次叠加内命中，返回对应次数；否则返回 -1。

整体时间复杂度降为O(M + N)，空间复杂度O(N)（前缀函数数组）。KMP 的核心思想是匹配失败时利用已匹配部分的前后缀信息回退，避免指针回溯，适合b较长、重复匹配开销大的场景。

思路 B：Rabin-Karp 滚动哈希

Rabin-Karp（RK）算法将字符串映射为哈希值，用滚动哈希在O(1)时间内滑动窗口：

1. 计算b的哈希值hash_b（多项式哈希，如hash = Σ s[i] * base^i mod mod）；
2. 在text = a * k上从左到右滑动长度为len(b)的窗口，每次用滚动公式更新窗口哈希，与hash_b比较；
3. 哈希相等时再做一次逐字符确认以消除哈希碰撞，命中即返回。

其期望时间复杂度为O(M + N)，但存在哈希碰撞导致的额外确认开销，最坏情况下退化到O(M * N)，因此工程上常与 KMP 结合使用或作为快速预筛。

两种方案都能与本题「有限解空间 + 窗口匹配」的框架无缝衔接：先定窗口（上界推导），再做一次线性匹配，从而把题目从平方级优化到线性级。

在仓库中的位置与延伸阅读

• 本题解原文位于 problems/686.repeated-string-match.md；
• 该题收录于仓库总目录 SUMMARY.md 与分类合集 collections/medium.md（Medium 难度），也是 README.md 题解列表的组成部分；
• 字符串匹配算法体系可参考 thinkings/basic-algorithm.md「字符串问题」一节，其中列举了朴素、KMP、RK、BM、trie 等匹配算法；
• 如需深入字符串子串类问题的更多思路，可继续阅读仓库中 trie 专题 与 字符串问题专题。

结语

LeetCode 686 表面上是一道「重复叠加字符串」的模拟题，本质上考察的是解空间边界推导这一算法思维：先用集合预判排除无解，再用周期串性质推导出叠加次数的上界2 * len(a) + len(b)，最后在有限范围内完成子串匹配。掌握「先定解空间、再设计出口」的方法后，你不仅能 AC 本题，还能把它推广到任何存在隐性无限循环的搜索类问题中。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode