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的情況呢榨乎。那么就是當A的長度已經大于等于B時募判，至少再一次append(A)就會有B為substring, 否則永遠不能形成麻养。

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;
    }
}

當然，用built-in非常的慢侄榴，僅超過了37%的人洞坑。因為Java中的String.contains用的都是最原始的brute-force, 時間復雜度達到O(m*n)

有一種很巧妙的辦法拙毫，首先建立b的prefix table(根據KMP算法)依许， 然后把a視為循環(huán)數組缀蹄。判斷是否有a[(i+j) % a.length]==b[j]。最后輸出的重復次數為(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;
    }
}

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