题目

https://leetcode.com/problems/repeated-string-match/

题解

套了 KMP 模板，O(n) 复杂度。分析如下。

class Solution {
    public int repeatedStringMatch(String a, String b) {
        int repeatedTimes = Math.max((int) Math.ceil((float) 2 * b.length() / a.length()), 2);
        int index = indexOf(a.repeat(repeatedTimes), b);
        if (index == -1) return -1;
        return (int) Math.ceil((float) (index + b.length()) / a.length());
    }

    // KMP, find index of s2 from s1
    public static int indexOf(String s1, String s2) {
        if (s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()) {
            return -1;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int x = 0;
        int y = 0;
        // O(M) m <= n
        int[] next = nextArray(str2);
        // O(N)
        while (x < str1.length && y < str2.length) {
            if (str1[x] == str2[y]) {
                x++;
                y++;
            } else if (next[y] == -1) { // y == 0
                x++;
            } else {
                y = next[y];
            }
        }
        return y == str2.length ? x - y : -1;
    }

    public static int[] nextArray(char[] str2) {
        if (str2.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2; // 目前在哪个位置上求next数组的值
        int cn = 0; // 当前是哪个位置的值再和i-1位置的字符比较
        while (i < next.length) {
            if (str2[i - 1] == str2[cn]) { // 配成功的时候
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}