算法——KMP初识

思想及探究看文末参考链接
得到next数组的代码
(思想上的巨坑，一直理解next[0]表示的是匹配字符串第零位对应部分匹配值，后来才发现next[0]表示的是第零位前面的最大匹配数，所以才初始为-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等类似字符串计算next时的优化
                    next[j] = k;
                } else {
                    next[j] = next[k];
                }
            } else {//运用递归思想
                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算法 零基础可看懂
从头到尾彻底理解KMP 从简至深(作者重新整理过但还是有点乱)，到扩展BM算法和Sunday算法