java - 构造子串的字符串操作

Question

给定一个由 N 个字符组成的字符串 A 和一个由 M 个字符组成的字符串 B，返回必须声明 A 以使 B 是重复字符串的子字符串的次数。如果 B 永远不可能是重复 A 的子串，那么您的函数应该返回 -1。

例如:

A = "abcd"
B = "cdabcdab"

函数应该返回 3，因为在声明字符串 A 三次之后我们得到了字符串“abcdabcdabcd”。字符串 B 是该字符串的子字符串。

尝试:目前卡在此处 - 在我开始编写代码之前先尝试构建和算法 - 真的可以在这里使用推送。我正在尝试考虑最小长度 A 必须在它包含 B 作为子字符串之前。不确定这是否是正确的方法。

Answer 1

思路是先一直自追加A，直到变大或者等于B(姑且称之为A+)。这将处理 B 完全位于 A+ 内的情况。 如果不是，则这是 B 从前面或后面环绕 A+ 的情况。对于正面包装，在 A+ 前加上 A，对于背面包装，在 A+ 后缀上加上 a。在每一次包装后检查 B 现在是否是 A+ 的子串。如果 B 现在不是子串，那么它永远不会是。

这是 Java 中的解决方案。

private static int times(String A, String B) {      

    StringBuffer aPlus = new StringBuffer(A);
    int times = 1;
    while (aPlus.length() < B.length()) {
        aPlus.append(A);
        times++;
    }

    if (aPlus.indexOf(B) != -1) {
        return times;
    }

    // prefix 
    aPlus.append(A);
    if (aPlus.indexOf(B) != -1) {
        return ++times;
    }

    //suffix
    aPlus.insert(0, A);
    if (aPlus.indexOf(B) != -1) {
        return ++times;
    }
    return -1;
}