KMP算法

public int KMPSearch(String s, String subStr) {
        int[] next = generateNext(subStr);

        int i = 0; // full string index
        int j = 0; // sub string index
        int n = s.length();
        while (i < n) {
            if (s.charAt(i) == subStr.charAt(j)) {
                i++;
                j++;
            } else if (j > 0) { // j > 0 才需要回退
                j = next[j - 1];
            } else {
                i++;
            }
            if (j == subStr.length()) { // 如果子串索引j已经到了子串末尾
                return i - j;
            }
        }
        return -1;
    }

    private static int[] generateNext(String str) {
        if (str.isEmpty()) {
            return null;
        }
        int[] next = new int[str.length()];
        next[0] = 0;
        int n = str.length();
        int prefixLen = 0;
        int i = 0;
        while (i < n) {
            if (str.charAt(i) == str.charAt(prefixLen)) {
                next[i++] = ++prefixLen;
            } else {
                if (prefixLen == 0) { // 既不相等，共同前后缀又是0
                    next[i++] = 0;
                } else {
                    prefixLen = next[prefixLen - 1];
                }
            }
        }
        return next;
    }