题目描述

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

例如：

  • a = "abcd", b = "cdabcdab" → 输出 3，因为 "abcdabcdabcd" 包含 "cdabcdab"。
  • a = "a", b = "aa" → 输出 2。

解题思路

题目要求找到最小的整数 k，使得 b 是 a 重复 k 次得到的字符串的子串。

核心分析

我们需要确定重复次数的上界。假设 a 的长度为 lenA，b 的长度为 lenB。

要让 b 成为子串，叠加后的字符串长度至少要为 lenB。最朴素的想法是：重复 ceil(lenB / lenA) 次。但考虑到 b 可能跨越 a 的边界（即 b 从前一个 a 的尾部开始，延伸到下一个 a 的前部），我们需要在首尾各多加上一个完整的 a。

因此，最多需要重复 (lenB / lenA) + 2 次（或者更精确地说，ceil(lenB / lenA) + 1 次）。

算法步骤

  1. 计算 len = (lenB + lenA) / lenA + 1，即需要尝试的最大重复次数（上限）。
  2. 使用 StringBuilder 逐步拼接 a，每拼接一次就在当前累积字符串中判断是否包含 b。
  3. 如果在第 i 次拼接后找到了 b，直接返回 i（即拼接次数）。
  4. 如果遍历完所有可能的拼接次数仍未找到，返回 -1。

边界情况

  • 如果 b 为空字符串，根据题意返回 0。
  • 当 a 的长度大于等于 b 时，只需重复 1 到 2 次即可覆盖所有可能，代码中的循环上界保证了这一点。

为什么循环次数这么取？

设叠加后的字符串为 S = a + a + ... + a（共 k 次）。如果 b 是 S 的子串，那么 b 的起始位置一定在前 lenA 个字符中（或者说 b 最多跨越 k 个 a）。换句话说，如果重复 ceil(lenB / lenA) + 1 次都找不到，说明再重复更多次也不可能找到——因为再增加一个 a 只是在首尾增加了相同的内容，不会新产生 b 作为子串的可能性。

复杂度分析

  • 时间复杂度：O(n * m)，其中 n = lenA，m = lenB。最坏情况下需要拼接 m/n + 1 次，每次 contains 调用在 Java 中的复杂度为 O(lenA * k * lenB) 的朴素匹配。总体上约为 O(lenA * lenB)。
  • 空间复杂度：O(lenA * k)，StringBuilder 存储了叠加后的字符串，最大长度约为 lenA * (lenB / lenA + 1) ≈ lenB + lenA。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package code.J686;

public class J686 {
    public int repeatedStringMatch(String a, String b) {
        int lenA = a.length();
        int lenB = b.length();
        if(b.isEmpty()) return 0;
        int len = (lenB + lenA) / lenA + 1;
        StringBuilder sumA = new StringBuilder();
        for (int i = 0; i <= len; i++) {
            if (sumA.toString().contains(b)) return i;
            sumA.append(a);
        }
        return -1;
    }
}