前言
本篇为大家介绍KMP算法，力求用最白话，最通俗的文字让你学会KMP算法！！！
但是！！！第一次接触KMP的小伙伴可能仍然会在某些地方卡壳，请各位耐心，如遇看不懂的地方，请深呼吸，慢慢消化，小弟已经尽力讲的详细了！！抱拳！！
即便你觉得你看懂了，但可能你需要一两天才能真正吃透KMP，所以各位请不要着急
提示：是正在努力进步的小菜鸟一只，如有大佬还有更妙的解法欢迎评论区讨论~ 废话不多说，直接上干货！
文章目录
一、KMP算法是什么？
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。
以上是百度百科的概念，相信没学过 KMP 算法的小伙伴第一次看到都一脸懵逼，没关系，本篇将通俗的，白话的，详细的，让你学会 KMP ！
先看概念解释的第一句： “KMP 算法是一种改进的字符串匹配算法”
那么我们先了解一下最最最原始的 BF（暴力匹配）算法的过程：
什么是字符串匹配？
比如一个字符串：“abcababcabc” 作为主串
要在这个主串中找到 “abcabc” ，“abcabc” 被称作子串
利用 i 和 j 下标分别访问这两个字符串的字符
依次匹配，直到在主串中找到完整的子串
BF算法过程简述
当子串中的 “abcab” 匹配完之后，发现下一个字符 “c” 和主串的下一个字符 “a” 不匹配，那么BF算法就直接将 j 移动到子串的起点（如图）
用子串的第一个字符 “a” 去比较主串待比较的 “a”
虽然BF算法也可以实现字符串匹配，但还有需要改进的地方：
假设匹配子串时，多次中途匹配失败，每一次都需要从头（子串的头）再来，这就是缺陷
举一个通俗的栗子：你在跨栏比赛，中途跨栏失败了一次
BF算法就惩罚你，让你从起点重新跑
而KMP算法会为你安排一个合适的惩罚，可能是让你后退两米，可能让你后退20米，也有可能让你从头跑
KMP就一定程度上节省了你的体力
而在计算机中，节省了时间，提高了效率
下面我们看看KMP算法的思想
二、解析KMP算法
1.KMP算法的思想
我们还拿刚刚的字符串 “abcababcabc” 举例 如图所示
再换句话强调一下这样移动的目的：
匹配失败后，在主串已经匹配成功的一部分中找到和子串最大程度已经匹配的一部分
这一部分就是此时主串的绿色方块和子串的蓝色方块
这是理解KMP算法的第一步！万事开头难，如果你理解了这个思想，就离胜利不远了！！
蓝色方块和绿色方块的长度专业术语是 “前缀和后缀最长相等长度”
j 移动的过程专业术语是 “回溯”
本篇不需要这些专业名词，跟着作者的思路你也能理解！
然后问题紧接着来了，程序是如何知道 j 移动到哪里的？
首先，我们获取主串和子串中的字符是利用 charAt() 这个方法：
字符串变量名 + 点号 + charAt（下标）
String str = "ababcabcdabcdefg";
char ch1 = str.charAt(0);
char ch2 = str.charAt(1);
System.out.println(ch1);// 结果为 a
System.out.println(ch2);// 结果为 b
然后，子串对应着有一个next数组，数组中存放数字
注意，next数组是和子串绑定的
上图中，子串里，绿色方块后的字符 “c” 对应的next数组中就存了一个数字 2 ，那么 j 移动的时候就移动到字符串中下标为 2 的位置去
这就是next数组的作用，它相当于一个告示牌，告诉 j 匹配失败后该去哪里
还记得我刚才举的跨栏的栗子嘛
如果我在第 5 个障碍栏处摔倒，这个障碍栏上写了个数字 2 ，那我就从第2个障碍栏开始重跑，而不是从0开始
如果我就是倒霉蛋，摔倒处的障碍栏上写个0，那我就得从0开始重跑了咯
同时next数组就是KMP算法的核心
那么next数组中存放的数字如何求得呢？
2.next数组（核心）
刚才说到：
子串里，绿色方块后的字符 “c” 对应的next数组中就存了一个数字 2
为什么是 2 呢？为啥不是 3 ？不是 0 ？
问题又来了，蓝色方块和绿色方块是我肉眼找出来的，那么程序是如何找到蓝色方块呢？换句话说说，程序如何计算 j 移动到的下标位置是几呢
接下来就要解析一下next数组的计算规则
我们用肉眼推导出来了next数组
next[0]为什么是 -1 ，next[1]为什么是 0 ，咱们待会再说
我知道你可能很急，但你先别急
但在代码里应该是先定义一个和子串长度相等的数组，然后写一个getNext方法计算next数组中的值，那么getNext方法如何写呢，我们用数学公式推理一下
1. 新的变量K
所以k一直就是我们所说的，j移动（回退）到的位置，
2.charAt(j - 1) == charAt(k)
3.charAt(j - 1) != charAt(k)
通过这两种情况的情况的对比分析可知
1，第一种情况才是正常的，理想的，我们希望发生的
2，如果发生第二种情况，我们就想办法改变现状，变成第一种情况，就是让 k 一直回退，每次回退之后就判断满足第一种还是第二种条件，直到满足第一种情况的条件为止
至此我们已经用肉眼和代码的方式分析了next数组的计算过程
现在趁热打铁，上代码解析！
4.分析next[0]和next[1]的取值（重点）
超级重点来啦！！！
前面我们遗留了 next[0]为什么是 -1 和 next[1]为什么是 0 这两个问题
小伙伴们仔细看！
三、KMP算法完整代码
public static void getNext(int[] next, String sub) {
next[0] = -1;
next[1] = 0;
int k = 0;
int j = 2;
while(j < sub.length()) {
if(k == -1 || sub.charAt(j - 1) == sub.charAt(k)) {
next[j] = k + 1;
j++;
k++;
}else {
k = next[k];
}
}
}
public static int KMP(String str, String sub, int pos) {
// 判断两个串不能为空
if(str == null || sub == null) {
return -1;
}
int i = pos;// i遍历主串 从pos位置开始
int j = 0; // j遍历字串 从0开始
int strLength = str.length();
int subLength = sub.length();
if(strLength == 0 || subLength == 0) {
return -1;
}
// 判断pos位置合法性
if(pos < 0 || pos > strLength) {
return -1;
}
//求字串的next数组
int[] next = new int[subLength];
getNext(next,sub);
while(i < strLength && j < subLength) {
if(j == -1 || str.charAt(i) == sub.charAt(j)) {
i++;
j++;
}else {
j = next[j];
}
}if(j == subLength) {
// 字串遍历完之后 j应该等于sublength
// 找到返回字串在主串中的起始位置
return i - j;
}else {
// 找不到返回-1
return -1;
}
}
public static void main(String[] args) {
String str = "ababcabcdabcdefg";
String sub = "gba";
int pos = KMP(str,sub,0);
System.out.println(pos);
}
需要注意，在KMP方法中：
while(i < strLength && j < subLength) {
if(**j == -1** || str.charAt(i) == sub.charAt(j)) {
这里判断 j == -1 是为了：
如果子串第一个字符（g）就匹配失败（main方法里设置的子串就是这种情况）
会执行下面的else语句：j = next[ j ]，而next[ j ]就是next[ 0 ]啊，所以此时 j 会被赋值为-1
再进入while循环时，因为 if 判断条件中有 j ==-1，所以进入这个if语句
i 和 j 都加1，仔细想一下，即是主串中的 i 已经向后走了一个，而 j 还在子串的第一个字符（g）处，就这样在主串中找是否有一个字符和子串的第一个字符（g）匹配
i 一直在遍历主串，而 j 一直在g的位置，当主串遍历完后，找不到则返回 -1；
总结
以上就是KMP算法的全部内容啦，主要有以下几个重点：
1，理解KMP算法的思想
2，next数组的计算（ k 的值）
3，next[ 0 ] 和 next[ 1 ]
4，判断 j == -1 的情况
如果本篇对你有帮助，请点赞收藏支持一下，小手一抖就是对作者莫大的鼓励啦~
上山总比下山辛苦
下篇文章见