什么是KMP算法
KMP是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。
KMP算法要解决的问题是在字符串中找到模式串的位置。平时常见的关键字搜索，模式串就是关键字，如果它在一个主串中出现，则返回它的具体位置，如果不存在就返回-1。
例子
例如要在主串ABCABCABDJK中找到模式串ABCABD的位置。
模式匹配的暴力求解
-
看到这个问题，一个很直观的思路就是逐一比对，相同则继续比较下去，不同则错一位重复比对操作。
当比较到
C != D时，令主串的下一个元素作为头继续和模式串比较。暴力求解的时间复杂度是O(n * m) 从我们人的角度来看，我们估计会直接将主串和模式串以下图这样对齐然后比较。
直接就跳过很多步了，而这正是KMP算法要做的。
KMP算法求解
在讲KMP算法之前，先讲一讲字符串的前缀和后缀。
例如字符串ABCABD，规定前缀不能包含最后一个字符，后缀不能包含第一个字符。那么字符串ABCABD的前缀有A，AB，ABC，ABCA，ABCAB；后缀有BCABD，CABD，ABD，BD，D。最长的前后缀相等的字符串就是AB，因此称2为字符串ABCABD的最长前缀后缀。
- 在进行字符串匹配前，需要算出模式串中以每个字符结尾(不包含当前字符)的next数组，该数组表示以当前字符结尾的字符串的最长前后缀长度。
以字符串ABCABD为例，
定义一个next数组，int[] next = new int[5]- 以
A结尾，next[0] = -1 - 以
B结尾，那就是A的最长前缀后缀，next[1] = 0 - 以
C结尾，那就是AB的最长前缀后缀，next[2] = 0 - 以
A结尾，那就是ABC的最长前缀后缀，next[3] = 0 - 以
B结尾，那就是ABCA的最长前缀后缀，next[4] = 1 - 以
D结尾，那就是ABCAB的最长前缀后缀，next[5] = 2
- 以
- next数组求解
- next[0] = -1，next[1] = 0
- i >= 2时，
定义一个变量cn表示跳到的位置，如上图跳到的位置是cn = next[i - 1](i - 1位置最长前缀的下一个位置)
如图，要求next[i]的值，我们要借助next[i - 1]的值，首先比较pattern[i - 1] 和 pattern[cn]，如果相等，那么显然next[i] = ++cn；如果不等，cn会往前跳，举个合适的例子如下图
如上图，pattern[cn] != pattern[i - 1]，那么cn会更新变成cn = next[cn]，变成下图位置
此时重复
pattern[cn] 和 pattern[i - 1]的比较，显然pattern[cn] == pattern[i - 1]，则next[i] = ++cn。(如果
cn跳到不能再往前跳，next[i] = 0)
这个过程的代码如下
next[0] = -1;
next[1] = 0;
int cn = 0;
int i = 2;
while(i < arr.length){
if(arr[i - 1] == arr[cn]){
next[i++] = ++cn;
}else if(cn > 0){
cn = next[cn];
}else{
next[i++] = 0;
}
}
- 有了这个next数组，我们就可以充分利用已经比较过的信息。
接下来举个例子说明如何使用next数组的信息。
定义两个标记i和j，逐一比较，如果str[i] == pattern[j]，则i++,j++；如果str[i] != pattern[j]，那么就可以使用next数组的信息了，上图的位置str[i] != pattern[j]，j位置的最大前缀后缀为3，那么j就跳到3位置继续和str的i位置比较下去。特别地，如果刚好j位置是0，也就是next[j] == -1，即第一个位置就不匹配了，那么i指针后移一位，继续。
(循环条件：i < str1.length && j < pattern.length)
