题解 | #kmp算法#

/**
     * 计算模式串匹配次数：
     * 模式串最后一个匹配完后，相当于模式串最后一个字符串+1的位置继续和主串匹配，
     * 只是没有匹配上，i = next[i], i回到模式串T的next[i]位置，j不变，总数加一。
     *               i
     * 编号  1 2 3 4 5
     * T    a b a b
     * next 0 1 1 2 3
     * S    a b a b a b
     *              j
     * <p>
     *              i(i=编号3)
     * T        a b a b
     * S    a b a b a b
     *              j
     *
     * @param S 模式串
     * @param T 主串
     * @return
     */
    public static int kmp(String S, String T) {
        // write code here
        int ans = 0;
        char[] charS = S.toCharArray();
        char[] charT = T.toCharArray();
        int[] next = getNextChar(charS);
        System.out.println(JSONObject.toJSONString(next));
        int i = 1, j = 1;
        while (j <= T.length() && i <= S.length()) {
            if (i == 0 || charT[j - 1] == charS[i - 1]) {
                ++i;
                ++j;

            } else {
                i = next[i];
            }
            if (i > S.length()) {
                ans++;
                i = next[i];
            }
        }
        return ans;
    }

    /**
     * 需要把最后以一位+1的next计算出来
     * a b a b
     * 0 1 1 2 3
     * next[j]的含义是：在子串的第j个字符于主串发生失配时，则跳到子串的next[j]位置重新于主串当前位置进行比较。
     *
     * @param T
     * @return
     */
    public static int[] getNextChar(char[] T) {
        int len = T.length;
        int[] next = new int[len + 2];
        int i = 1, j = 0;
        next[1] = 0;
        while (i <= len) {
            if (j == 0 || T[i - 1] == T[j - 1]) {
                ++i;
                ++j;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }