题目

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

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

解答

package Com.Xu.String;

public class SixEightSix {
public static int repeatedStringMatch(String a, String b) {
int n=a.length();
int m=b.length();
int index=strStr(a,b);
if(index==-1){
return -1;
}
if(n-index>=m){
return 1;
}
return (m+index-n-1)/n+2;
}

public static int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    if (m == 0) {
        return 0;
    }
    int[] pi = new int[m];
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
            j = pi[j - 1];
        }
        if (needle.charAt(i) == needle.charAt(j)) {
            j++;
        }
        pi[i] = j;
    }
    for (int i = 0, j = 0; i - j < n; i++) { // b 开始匹配的位置是否超过第一个叠加的 a
        while (j > 0 && haystack.charAt(i % n) != needle.charAt(j)) { // haystack 是循环叠加的字符串，所以取 i % n
            j = pi[j - 1];
        }
        if (haystack.charAt(i % n) == needle.charAt(j)) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

public static void main(String[] args) {
    String a="abc";
    String b="cabcabca";
    System.out.println(repeatedStringMatch(a,b));
}

}

解答

示例: a = "abcd", b = "cdabcdab"
b的组成如下 cd + 1个 abcd + ab
故需要a的个数为
(bn - (an - index) - 1 / an) + 2 即 (bn + index - an - 1) / an + 2
其中an-index为cd的长度
因为不知道cd abcd ab后面是否存在ab这个尾巴, 所有统一减1计算需要a的个数
cd需要a一个, 尾巴ab需要a一个, 故还要+2
所以结果为 (bn + index - an - 1) / an + 2