Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:
The length of A and B will be between 1 and 10000.

一刷
題解：
用string built-in方法，但是怎么判斷-1的情況呢。那么就是當(dāng)A的長度已經(jīng)大于等于B時(shí)，至少再一次append(A)就會(huì)有B為substring, 否則永遠(yuǎn)不能形成。

class Solution {
    public int repeatedStringMatch(String A, String B) {
        int count = 0;
        StringBuilder sb = new StringBuilder();
        while(sb.length()<B.length()){
            sb.append(A);
            count++;
        }
        if(sb.contains(B)>=0) return count;
        if(sb.append(A).contains(B)>=0) return ++count;
        return -1;
    }
}

當(dāng)然，用built-in非常的慢，僅超過了37%的人。因?yàn)镴ava中的String.contains用的都是最原始的brute-force, 時(shí)間復(fù)雜度達(dá)到O(m*n)

有一種很巧妙的辦法，首先建立b的prefix table(根據(jù)KMP算法)， 然后把a(bǔ)視為循環(huán)數(shù)組。判斷是否有a[(i+j) % a.length]==b[j]。最后輸出的重復(fù)次數(shù)為(i + j) / a.length， j為b的index

class Solution {
    public int repeatedStringMatch(String A, String B) {
        int[] prefTable = new int[B.length()+1];
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        //KMP algorithm
        for(int i=1, j=0; i<b.length;){
            // prefix table for B
            if(b[j] == b[i]) j++;
            else j = prefTable[j];
            prefTable[i] = j;
            i++;
        }
        System.out.println(Arrays.toString(prefTable));
        
        for(int i=0, j=0; i<a.length; i+=Math.max(1, j-prefTable[j]), j=prefTable[j]){
            while(j<b.length && a[(i+j) % a.length]==b[j]) j++;
            if(j == b.length){
                if((i+j)%a.length == 0) return (i + j) / a.length;
                else return (i + j) / a.length+1;
            }
        }
        return -1;
    }
}

還有一個(gè)很自然的思路：KMP+循環(huán)數(shù)組，留給二刷