首先声明所有数组第一个下标从0开始。(有些教程会选择从1开始，先说清楚，以免搞混了)。
这里我们使用一个例子来简单说明一下
例如
如果我们用暴力寻找的话，那么过程是
总共比对了 4 + 1 + 1 + 1 + 7 + 1 +1 + 1 + 3 + 1 + 1 + 8 +1 +1 +1 +8 = 41 (次)
如果改进成KMP的话，那么运算过程就是(灰色地方是KMP算法不去考虑的地方，红点是每次比较的字符串位置)
?
总共比对了 4 + 1 + 7 + 1 + 1 +8 + 4 = 26 (次)
如果我们看红点在abcxabcdabxabcdabcdabcy的位置，我们就会发现红点一直在向前移动，不会往后退/回头。这就是KMP算法的优点即不会倒退(也有人称作回溯)，所以就能避免不必要的匹配检查。
让我们依次看看KMP算法在上面的例子中都做了些什么。
首先让我们看一下第一个例子。
绿框中是KMP算法跳过的地方，那么我们就来对比一下两个红框里面的内容。
这里我们可以看到，深绿色方框那里是不相同字符的位置与新一轮判定的开始位置。
深橘黄色方框里的是已经匹配成功的字符串 abc。
关键的地方来了，因为已经匹配成功的字符串abc中没有相同的前后缀，所以下一次比对要从abcdabcy的首位开始比较。
我们简单地来看一下abc的前后缀情况（ac写错了，是bc）
要注意，这里我们看的前后缀的长度要小于已匹配到的字符串长度，因为如果长度一样了那就不用分前后缀了，也没有比较的意义了。
因为没有相同的前后缀，我们就不用担心错过什么，直接从配对失败的地方开始新的匹配就行了。
这个很好理解，让我们假设一下如果在上面这个例子中间有这么一种情况
在这里如果符匹配条件我们至少需要满足方框内的字符相同。
让我们看看方块内的字符处于abc中的什么位置
在黄色框内，bc属于abc的后缀，ab属于abc的前缀，所以如果条件符合的话，abc需要有相同的前后缀。
不理解为什么的同学不用担心，现在只要记住我们在寻找相同前后缀就行了，一会看完应该就能想通了。
让我们看看下一个例子。
在这个例子中KMP算法跳过了绿色方框的部分，直接运行了红色方框里的内容。让我们看看红色方框里发生了什么。
深绿色方框位置是不相同字符位置与新一轮比较的位置。
深橘黄色方框里的是已经匹配的字符串 abcdab。
让我们来找一下 abcdab的前后缀吧。
我们发现abcdab有相同的前后缀。
重点又来了，如果有相同的前后缀，我们就需要把前缀移动到后缀的位置上。
这样abcdabcy就向右移动了四位，然后开始比较abcdabcy[相同前后缀长度] 上的字符，即第3个字符c(默认索引从0开始)。
不明白没有关系，我们再看两个例子。
在上面这个例子中，绿色依然是被忽略的部分，红色方框是KMP算法执行的部分。
让我们继续关注红色方框里的内容
深绿色的地方是匹配到不一样字符的位置，也是下一次比较的开始位置。
深橘色的地方是已经成功匹配的字符串ab。
由于ab没有相同的前后缀，所以下一次比较从abcdabcy[0] 开始。
最后我们看看这个例子
依旧只看红色方框部分
深绿色的地方是匹配到不一样字符的位置，也是下一次比较的开始位置。
深橘色的地方是已经成功匹配的字符串abcdabc。
让我们来看看abcdabc的前后缀吧。
我们发现abcdabc有相同的前后缀abc，我们就需要把前缀移动到后缀的位置上。
这样abcdabcy就向右移动了四位，然后开始比较abcdabcy[相同前后缀长度] 上的字符，即第3个字符d(默认索引从0开始)。
最后我们比对发现找到了目标字符串。
通过上面的例子，我们发现每当我们匹配失败，就需要寻找匹配成功的字符串中有没有相同的前后缀（最长的前后缀），然后再判定下一次比较要从哪一位开始。
逻辑实现：
还是回到上面的例子，如果每次匹配失败都去判定一次是否有相同前后缀的话，那么就太麻烦了，所以我们可以在匹配前就把各种情况的前后缀找出来。
上面是我们能列举出来的所有情况，KMP算法需要的关键信息就是最左边的匹配数与最右边的前/后缀长度。
因为8匹配就匹配完成，所以我们其实只需要考虑0～7匹配的情况，总共8种情况。
我们可以用一组数组来保存此数据，我们命名此数组为next数组。
int[] next = new int[] { 0,0,0,0,0,1,2,3};
所以每当我们匹配失败的时候，我们就可以通过next数组来快速定位下一个需要对比的索引位置。
这样我们的KMP算法可以理解为
KMP(string target, string txt){
1）计算next数组
2）通过循环来对比target与txt字符串
}
总之，在不匹配的时候主串不会前移，要么模式串前移到前后缀长度的位置，要么主串后移一位。
public void kmp(String haystack, String needle){
int[] next = getNext(needle);
int hi = 0; // 主串的索引
int ni = 0; // 模式串的索引
while (hi < haystack.length()){
if (haystack.charAt(hi) == needle.charAt(ni)){
hi++;
ni++; // 相等，各进一步
}else if(ni > 0){
ni = next[ni - 1]; // 失配，若模式串索引大于0，则根据next数组移动模式串
}else {
hi++; // 失配，若模式串索引等于0，则将主串后移一位
}
if (ni == needle.length()) {
System.out.println(hi - ni);
ni = next[ni - 1]; // 多个匹配位置
}
}
}
原文：https://www.cnblogs.com/shaolongdong/p/14127108.html