KMP算法：

昨天介绍了BF算法，今天则介绍其优化算法KMP算法，因为BF算法简单但效率较低，造成效率低是因为回溯。而今天介绍的KMP算法，尽量利用已经部分匹配的结果信息，尽量让 i 不回溯，加快模式串T的滑动速度。
##定义：
Knuth-Morris-Pratt字符串查找算法，简称为 KMP算法，常用于在一个文本串 S 内查找一个模式串 P 的出现位置。

前提：

kmp算法首先你要理解前缀是什么，后缀是什么？才能正式的往下继续做下去。
前缀：指除了最后一个字符以外，一个字符串的全部头部组合。
后缀：指除了第一个字符以外，一个字符串的全部尾部组合。

例子：

字符串：“abaab”
前缀：a,ab,aba,abaa
后缀：b,ab,aab,baab
最大长度：2（即前缀后缀的公共元素）

重点：

学会了前缀后缀之后我们要懂得一个最重点东西，那就是部分匹配值(next数组)。在我认为这是KMP最核心的东西。
模式串：ababc
图片说明
所以next数组=最大长度数组下标往右移动,然后初始值赋为-1，即next[]={-1,0,0,1,2}
知道next数组后就很好求了，将主串与子串进行匹配，当匹配失败的时候就看主串的不匹配元的next数组元素，移动已匹配元素个数-对应的next数组元素
###过程例子：
主串s="ababc"
子串t="abc"

第一趟 ababc
abcac
（a的next数组元素是0，所以移动2（已匹配元素个数）-0（对应的next数组元素）=0）

第二趟 ababc
abc

算法：

next数组：

void getNext(String pattern, int next[]) {
            int j = 0;
            int k = -1;
            int len = pattern.length();
            next[0] = -1;

            while (j < len - 1) {
                if (k == -1 || pattern.charAt(k) == pattern.charAt(j)) {
                    j++;
                    k++;
                    next[j] = k;
                } else {
                    k = next[k];
                }
            }

        }

2019/7/26

今天在csdn看到v_JULY_v写的从头到尾彻底理解KMP，让我受益匪浅，对于next数组的匹配过程有了更加深刻的理解，附上地址https://blog.csdn.net/v_july_v/article/details/7041827，特别是对于wudehua55555的那种图，令我理解的更容易啦！
还有对于next数组的算法的考虑还是相当的不足，应该说是优化吧。竟然还可以这样做！当p[j] = p[ next[j ]]的时候因为两者相等，会导致我们做了无用功，然后再继续一次的递归，即令next[j] = next[ next[j] ]。
优化算法：

void getNext(String pattern, int next[]) {
            int j = 0;
            int k = -1;
            int len = pattern.length();
            next[0] = -1;

            while (j < len - 1) {
                if (k == -1 || pattern.charAt(k) == pattern.charAt(j)) {
                    ++j;
                    ++k;
                    //System.out.println(" "+j+"、 " +k);
                    if(pattern.charAt(k) == pattern.charAt(j))
                        next[j] = k;
                    else next[j] = next[k];
                } else {
                    k = next[k];
                }
            }

        }

最后..其实我到现在也灭有理解++放前放后的区别，就只是省了一点空间嘛？hhhh

【算法】kmp算法

KMP算法：

前提：

例子：

重点：

算法：