重复叠加字符串 A 多少次才能包含 B？（LeetCode 686）

简化版

先把 A 重复到长度至少等于 B，检查是否包含；如果不包含，再多重复 1 次检查。原因是 B 可能横跨两个重复块边界，但当长度已经覆盖 B 后，最多再补一个 A 就能覆盖所有起点。包含检查可以用语言内置、KMP 或 Rabin-Karp。

详细版

int repeatedStringMatch(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int count = 0;
    while (sb.length() < b.length()) {
        sb.append(a);
        count++;
    }
    if (sb.indexOf(b) >= 0) return count;
    sb.append(a);
    if (sb.indexOf(b) >= 0) return count + 1;
    return -1;
}

若面试要求不用内置 indexOf，把包含判断替换为 KMP 即可。整体思路重点不是无限重复，而是证明只需要检查 ceil(|B|/|A|) 和再多 1 次。

完整版教学

一、为什么不能一直重复到找到为止

如果 B 根本不可能出现在重复后的 A 中，无限循环就结束不了。必须给重复次数一个上界。

例如：

A = "abcd"
B = "cdabcdab"

B 从第一个重复块的中间开始，跨过多个块，到第三个块中间结束，所以只看一次或两次不够。

二、最少先重复到什么长度

如果 B 要作为子串出现，承载它的长串长度至少要等于 B.length()。所以先重复到：

count = ceil(len(B) / len(A))

这时长串长度已经够放下 B，如果 B 的起点刚好不利，可能还需要跨过右侧一个块的边界，所以再检查 count + 1。

检查次数	覆盖的情况
`count`	B 完全落在当前重复串内部
`count + 1`	B 从某个 A 块中间开始，并延伸到下一块
更多次数	不会提供新的起点形态

三、为什么最多多加一次 A 就够

在无限重复串中，B 的起点只需要看它落在某个 A 块内的偏移。偏移只有 0..len(A)-1 这些可能。

当重复串长度已经至少为 len(B)，再额外加一个完整 A，就能覆盖所有起点偏移向右延伸 len(B) 的范围。再加更多 A 只是重复同样的偏移模式。

记住：无限重复串里的起点形态按 len(A) 周期重复，不需要真的构造无限串。

四、包含判断可以怎么做

最短实现可以用 sb.indexOf(b)。如果题目考字符串算法，可以换成 KMP：

boolean contains(String text, String pattern) {
    return text.indexOf(pattern) >= 0;
}

面试时说明：“这里的核心上界与匹配算法独立；匹配函数可以是内置、KMP 或 Rabin-Karp。”

五、提前剪枝是否必要

可以先判断 B 中是否存在 A 永远无法提供的字符。如果有，直接返回 -1。

A = "abc"
B = "abdc"

字符 d 不在 A 中，不可能匹配。这个剪枝不是必要条件，因为最终两次包含检查也会失败，但可以作为面试中的优化补充。

六、复杂度如何分析

构造出的字符串长度最多是 len(B) + 2 * len(A) 量级，包含检查若用 KMP 是线性的。若用 Java indexOf，现代实现通常很快，但面试复杂度最好按匹配算法说明。

构造长度 <= len(B) + len(A)
KMP 检查 O(len(B) + len(A))
空间 O(len(B) + len(A))

七、常见误区与追问

误区：只重复到长度大于等于 B 就停止。 B 可能从 A 块中间开始，需要再多检查 1 次。
误区：无限追加直到找到。 不存在答案时会失控，必须有次数上界。
误区：认为多加 2 次或更多才安全。 起点偏移按 A 的长度周期重复，多加 1 次已覆盖边界。
追问：为什么 count+1 后还没有就一定没有？ 所有可能起点偏移都已被覆盖，再往后只是重复同样偏移。
追问：能否不用构造大字符串？ 可以在 KMP 比较时用 A.charAt(i % lenA) 模拟无限串。
追问：复杂度取决于什么？ 取决于构造长度和包含匹配算法，KMP 下整体线性。

八、加强记忆

这题的关键不是“重复几次试试”，而是“重复串的起点偏移只有 len(A) 种”。先凑够 B 的长度，再多 1 个 A 覆盖跨边界情况。看到重复包含题，先写 while len < B，再检查当前和多一次，边界就稳。

简化版

详细版