KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。
KMP算法的时间复杂度O(m+n) 。
KMP的优点:
- 主串不回溯。
- Next数组的是“根据最长相同前后缀确定”。
- 根据子串的特点计算模式函数值，达到减少回溯的效果
说的简单的一点，就是一个用于在主串中，查找子串的算法。
暴力解法（BF）
在讲解KMP算法之前，我们得先理解暴力解法，因为KMP算法就是在暴力解法的基础之上，进行了优化，使之匹配速度加快。
人如其名，暴力解法，就是一种很暴力的解决方法。
比如：主串“abbabbec”，待查找的子串为“abbec”， 请问主串中是否包含这个子串？
我们肉眼，能够很轻松的看到从第4个字符开始，一直到末尾这一段，就是需要查找的子串。
那么编译器是如何进行查找呢？它就只能一个字符一个字符的尝试：
上图就是暴力解法的全部过程，通过匹配一个个字符，如果当前字符匹配成功，i和j就同时走一步。
如果当前字符匹配不成功，i 就应该回到当前开始的第一个字符的下一个字符：
比如图中步骤4和步骤5，就是说的这个意思，当前是从第一个字符a开始匹配的，此时匹配失败了，i就应该回到a字符的下一个字符，j就从0下标开始，继续往下匹配；
当i或者j走到了字符串的末尾，我们就结束循环。
然后判断j是不是遍历完了待查找的子串，如果确实是走到了子串的末尾，说明查找成功了，就返回子串在主串的起始位置（i - j， 在上图就是返回3）。
反之就是：主串的字符都遍历完了，子串的还没遍历完，那就是主串没有这个子串的情况，此时返回-1即可。
//BF算法
//s 为主串
//m 为待查找的子串
public int BF(String s, String m) {
if(s == null || m == null) {
return -1;
}
char[] str1 = s.toCharArray(); //主串
char[] str2 = m.toCharArray(); //子串
int i = 0; //指向主串的下标
int j = 0; //指向子串的下标
//i和j的值，都还没到末尾，循环继续
while (i < str1.length && j < str2.length) {
if (str1[i] == str2[j]) { //当前字符匹配成功
i++;
j++;
} else { //当前字符匹配不成功
i = i - j + 1; //回到开头的下一个字符
j = 0; //子串从头开始
}
}
//判断是否遍历完了子串，并返回相应的值
return j == str2.length? i - j : -1;
}
时间复杂度：
假设主串的长度为N， 子串的长度为M。
最差的情况，就如上图的情况，只有在最后一个字符才查找成功。
所以子串要从每一个字符作为起始位置开始匹配，每一个字符作为起始，都会匹配子串的长度M次，也就是说暴力解法的时间复杂度为O(N*M)。
KMP算法
KMP算法和BF算法，在代码上差别不大。
在BF的代码基础之上，需要计算一个next数组，
在while循环里面再加一个判断语句即可，其他的代码都是不变的。
虽然代码改动不是很大，但是从逻辑思维上，却是一个质的飞越。
所以我们先来看一下KMP的核心：next数组。
next数组究竟是什么？都会有这样一个疑问。
其实next数组，计算的待查找的子串的每个字符（不包括当前字符）,前面的所有字符中，前缀字符串和后缀字符串相等的，并且最长的字符个数。
比如：
举一个完整的例子
比如子串是str2 = “ababab”，计算这个字符串的next数组如下：
首先就是从头开始遍历字符串：（建议拿出笔和纸，一起画一画，更容易理解）
j = 0; str2[j] = a
a字符前面没有任何字符，人为规定第一个字符的next值为-1。
j = 1; str2[j] = b
b字符前面只有一个字符a，有人就会说，那么next就是1咯？
当然不是，我们还忽略了一个重要条件：
- 计算的当前字符前面的所有字符，
- 进行划分前缀和后缀字符串，
- 但是所谓的前缀和后缀字符串，并不包括了这前面的整体字符串。
说的简单一点就是：
假设b字符前面的所有字符是“abc”， 前缀字符串是“abc”， 后缀字符串是“abc”，这种情况是不算在内的。
用数学公式解释：前缀字符串 = 后缀字符串 = b字符前面所有字符。
这种情况不算数。
所以当前这个b字符，前面就只有一个字符，所以人为规定第二个字符的next值为0。
j = 2；
str2[j] = aa字符前面有字符串“ab”， 前缀和后缀字符串，排除“ab” = “ab”的情况，
就没有能够匹配前缀和后缀的字符串，所以第三个字符的next值为0。
j = 3;
str2[j] = bb字符前面的字符串是“aba”，此时排除“aba” = ”aba“的情况，
那就只剩下前缀字符串“a” = 后缀字符串“a”的情况，
所以第四个字符的next值为1。
j = 4;
str2[j] = aa字符前面的字符串是“abab”，排除“abab” = “abab”的情况后，
就只剩下前缀字符串“ab” = 后缀字符串“ab”的情况，
所以第五个字符的next值为2。
j = 5；
str2[j] = bstr2 = “ababab”
b字符前面的字符串是“ababa”， 排除“ababa” = “ababa”的情况后，
就只剩下前缀字符串“aba” = 后缀字符串“aba”，所以第六个字符的next值为3。
j = 6；
str2[j] = ‘\0'遍历结束
所以上面例子的next数组的值，如下图：
那么就有同学会纳闷了，在逻辑层面上，我知道该怎么计算next数组了，但是在代码层面上，似乎并没有什么思路。
不急，我们现在就说一下代码怎么实现这个逻辑。
我们以上图的最后一个字符b为例。
在求解b字符所对应的next值时，b字符前面的字符，是已经计算好了next值的。
所以我们需要借助b字符前面已经计算好的next值，来计算b字符的next值。
所以next数组的计算代码，如下：
public int[] getNextArr(String m) {
if (m.length() < 2) { //只有一个字符
return new int[] {-1};
}
if (m.length() < 3) { //只有两个字符
return new int[] {-1, 0};
}
char[] str = m.toCharArray();
int[] next = new int[m.length()];
next[0] = -1;
// 人为规定的两个位置的next值
next[1] = 0;
// 表示往前跳的下标。也就是前缀字符串的下一个字符。初始化就是第一个字符
int cn = 0;
// 从第三个字符开始判断
int i = 2;
while (i < m.length()) {
if (str[i - 1] == str[cn]) {
// 当前字符的前一个字符，与cn所对应的字符比较
// 等价于：next[i++] = next[i - 1] + 1; cn++;
// next[i++] = ++cn;
next[i++] = next[i - 1] + 1;
cn++;
} else if (cn > 0) {
// 说明当前字符没匹配成功，cn要往前跳，找上一组前缀、后缀字符串
cn = next[cn];
} else {
// cn一直往前跳，都没能与当前字符匹配成功，则当前位置next值就是0
next[i++] = 0;
}
}
return next; //返回next数组
}next数组的计算代码，我们就讲完了，再加把劲，就还剩最后的一点点了。
我们先来将大致的框架写出来：
//KMP算法
// s 为主串
// m 为待查找的子串
public int KMP(String s, String m) {
if (s == null || m == null || s.length() < 1 || m.length() < 1) {
return -1;
}
int[] next = getNextArr(m); //计算子串的next数组
char[] str1 = s.toCharArray();
char[] str2 = m.toCharArray();
int i = 0; //指向主串的下标
int j = 0; //指向子串的下标
while (i < str1.length && j < str2.length) {
//字符相等的情况，i和j同时加1
if (str1[i] == str2[j]) {
i++;
j++;
} else if (j == 0) {
} else {
}
}
return j == str2.length? i - j : -1; //判断子串是否遍历完了
}现在就还剩下while循环里面，20行~24行的代码，还没填写。
20行~24行的代码，是在上面的if语句没有为真，才会走到20行后面代码。
也就是说此时当前的字符已经没有匹配成功了。
此时就需要对j或者i进行调整。
那么对于j来说，就分为两个情况：
j ！= 0时，则说明j还能往前面跳，即就是说j位置前面的字符，还有可能会有前缀、后置字符串。
那么j继续往前跳即可。
j = next[j]。（找j位置前面的前缀字符串）
j == 0时，则说明j前面已经没有字符了，换个角度说，对于当前i位置的字符，
在子串中j已经走到了第一个字符，都还没匹配成功，则说明，当前i位置的字符肯定不会匹配成功的。
那么i往后走一个字符的位置，然后再循环就进行判断。
完整的代码：
//KMP算法
// s 为主串
// m 为待查找的子串
public int KMP(String s, String m) {
if (s == null || m == null || s.length() < 1 || m.length() < 1) {
return -1;
}
int[] next = getNextArr(m); //计算子串的next数组
char[] str1 = s.toCharArray();
char[] str2 = m.toCharArray();
int i = 0; //指向主串的下标
int j = 0; //指向子串的下标
while (i < str1.length && j < str2.length) {
if (str1[i] == str2[j]) { //字符相等的情况，i和j同时加1
i++;
j++;
} else if (j == 0) { //j不能再往前走了，那么i就往后走一个位置
i++;
} else { //j还能往前跳，寻找前面的前缀字符串
j = next[j];
}
}
return j == str2.length? i - j : -1; //判断子串是否遍历完了
}
只要理解了next数组是如何进行计算的，那么KMP算法的就理解了一大半了。
 |  |
|---|---|
| 后面的整体的代码框架，跟BF算法是差不多的。 | |
| 只需分为i和j两个值的调整，即可！ |
具体的，大家可以再分别举几个例子，自己手动去走一遍代码，这里就能更好的理解KMP算法的思路。
也可以看一下左程云老师所写的《程序员代码面试指南》一书，也有相应的讲解。
