686. Repeated String Match

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视为循环数组。判断是否有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+循环数组，留给二刷