686. Repeated String Match

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.

--------------------
为满足包含B的条件，A最多重复的次数不会超过B.length() + A.length() * 2

Solution #1, 暴力解
注意返回时的count的计算
O(m * n)

class Solution {
    public int repeatedStringMatch(String A, String B) {
        String s = A;
        while (s.length() <= B.length() + A.length()) {
            s += A;
        }
        
        for (int i = 0; i < s.length() - B.length() + 1; i++) {
            String sub = s.substring(i, i + B.length());
            if (sub.equals(B)) {
                return (i + B.length() + A.length() - 1) / A.length();
            }
        }
    
        return -1;
    }
}

Solution #2, 典型的KMP
理解的要点
1. 找每个点的longest proper preffix == longest proper suffix (proper的意思是string本身不能算＊ffix)
2. preprocess里是pattern自己比自己。主方法里是pattern对比A。2者的原理其实是一样的。
3. table里存的是proper的长度

class Solution {
    public int repeatedStringMatch(String A, String pattern) {
        int i = 0, j = 0;
        int[] table = preprocess(pattern);
        
        String s = A;
        while (s.length() < pattern.length() + A.length()) {
            s += A;
        }
        
        while (i < s.length()) {
            if (s.charAt(i) == pattern.charAt(j)) {
                j++;
                i++;
                if (j == pattern.length()) break;
            }else if (j > 0) {
                j = table[j - 1];
            }else {
                i++;
            }
        }
        System.out.println(i);
        if (i == s.length()) return -1;
        return (i + A.length() - 1) / A.length();
    }
    
    private int[] preprocess(String s) {
        int[] table = new int[s.length()];
        int j = 0, i = 1;

        while (i < s.length()) {
            if (s.charAt(j) == s.charAt(i)) {
                table[i] = j + 1;
                j++;
                i++;
            }else if (j > 0) {
                j = table[j - 1];
            }else {
                i++;
            }
        }
        
        return table;
    }
}