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。示例输入输出说明a abcd,b cdabcdab3a叠加三遍为abcdabcdabcd此时b是其子串a a,b aa2叠加两遍为aaa a,b a1叠加一遍即匹配a abc,b wxyz-1无论如何叠加都不包含约束条件1 a.length 10^41 b.length 10^4a和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这一判断可以在叠加开始前直接排除大量无解用例例如示例 4a abc,b wxyzw、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 abacb包含字符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 abcabcabcabcabc5 个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**bbababa恰好被包含在其中。这里下界循环次数为⌈(6 2 - 1)/2⌉ ⌈7/2⌉ 4而实际需要 5 次比下界多循环了两次。除此之外没有别的可能。为什么最多只多两次因为叠加串是周期性的当叠加串长度达到len(b)后b的匹配起点只能落在a的某一周期内起点最多偏移一个a的长度匹配终点最多再延伸一个a的长度再多叠加只会重复已有周期不会产生新的匹配机会。由此得出结论实际循环次数n不会大于「下界循环次数 2」因此叠加串长度的临界值就是2 * len(a) len(b)。超过这个范围再多次叠加也没有意义——这就是循环终止的出口。最终解法Python 实现与复杂度分析代码支持Pythonclass 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。思路 AKMP 单次扫描构造长度不超过2 * len(a) len(b)的叠加串后只需调用一次 KMP 匹配无需逐次叠加、逐次重扫先对模式串b预处理出next前缀函数数组复杂度O(N)在目标串text a * k上执行一次 KMP 扫描复杂度O(len(text)) O(M N)若在k次叠加内命中返回对应次数否则返回 -1。整体时间复杂度降为O(M N)空间复杂度O(N)前缀函数数组。KMP 的核心思想是匹配失败时利用已匹配部分的前后缀信息回退避免指针回溯适合b较长、重复匹配开销大的场景。思路 BRabin-Karp 滚动哈希Rabin-KarpRK算法将字符串映射为哈希值用滚动哈希在O(1)时间内滑动窗口计算b的哈希值hash_b多项式哈希如hash Σ s[i] * base^i mod mod在text a * k上从左到右滑动长度为len(b)的窗口每次用滚动公式更新窗口哈希与hash_b比较哈希相等时再做一次逐字符确认以消除哈希碰撞命中即返回。其期望时间复杂度为O(M N)但存在哈希碰撞导致的额外确认开销最坏情况下退化到O(M * N)因此工程上常与 KMP 结合使用或作为快速预筛。两种方案都能与本题「有限解空间 窗口匹配」的框架无缝衔接先定窗口上界推导再做一次线性匹配从而把题目从平方级优化到线性级。在仓库中的位置与延伸阅读本题解原文位于 problems/686.repeated-string-match.md该题收录于仓库总目录 SUMMARY.md 与分类合集 collections/medium.mdMedium 难度也是 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考