KMP算法

暴力匹配在匹配失败中断后，重新找位置。KMP在这里做了优化。在这里利用已匹配的部分字符串，其实可以分析出正确位置出现的一个前提条件，就是是在已匹配的部分字符串的前后缀可重合。我们先让新的匹配索引满足前后缀可重合条件，再去继续匹配，可提高匹配效率。

下面是生成部分匹配表的代码，即计算字符串每个位置最大前后缀匹配值。

双指针算法，i表示当前在计算哪个元素的最大匹配值，j表示当前元素的最大匹配值。

核心点解读：在比较新的i和j时，遇到失败（不相等）情况，需要妥协，在已匹配的j-1个字符串中找个新的最大重合前后缀位置即next[j-1]，然后继续尝试匹配。

    //获取到一个字符串(子串) 的部分匹配值表
    public static  int[] kmpNext(String dest) {
        //创建一个next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
        for(int i = 1, j = 0; i < dest.length(); i++) {
            //当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
            //直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
            //这时kmp算法的核心点
            while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j-1];
            }
            
            //当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }