思想及探究看文末參考鏈接
得到next數(shù)組的代碼
(思想上的巨坑，一直理解next[0]表示的是匹配字符串第零位對應(yīng)部分匹配值，后來才發(fā)現(xiàn)next[0]表示的是第零位前面的最大匹配數(shù)，所以才初始為-1)

private static int[] genNext(String p) {
        char[] chars = p.toCharArray();
        int length = p.length();
        int[] next = new int[length];

        int k = -1;
        int j = 0;
        next[0] = k;

        while (j < length - 1) {
            if (k == -1 || chars[j] == chars[k]) {
                k++;
                j++;
                if (chars[j] != chars[k]) {//對abab,abcabc等類似字符串計(jì)算next時的優(yōu)化
                    next[j] = k;
                } else {
                    next[j] = next[k];
                }
            } else {//運(yùn)用遞歸思想
                k = next[k];
            }
        }

        return next;
    }

字符串匹配代碼

private static int indexOfString(String s, String p) {
        int[] next = genNext(p);
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        int sLen = s.length();
        int pLen = p.length();
        int i = 0, j = 0;

        while (i < sLen && j < pLen) {
            if (j == -1 || sChars[i] == pChars[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        return j == pLen ? i - j : -1;
    }

參考鏈接

字符串匹配的KMP算法 零基礎(chǔ)可看懂
從頭到尾徹底理解KMP 從簡至深(作者重新整理過但還是有點(diǎn)亂)，到擴(kuò)展BM算法和Sunday算法