图解KMP算法
题目
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
要找出符合的字符串，最暴力的方法是通过两个for循环来解决。
首先我们设置needle[0] 与haystack[0] 左边对齐比较，如果相同就比较 needle[1] 与haystack[1]，如果不相同则让needle右移一位，使needle[0] 与haystack[1] 对齐比较。如图所示以此类推，直至找到结果。
这么做的结果是每次needle比较失败，都会往后移动一格，然后重新从头开始比较。最差的结果就是每次比对到最后一个才发现不对，这样就要从第一位开始比对起，所以最坏的打算就需要O(m*n)。
为了优化这个方法，我们可以采用KMP(The Knuth-Morris-Pratt Algorithm)算法，这样我们可以更快一点解决问题，优化算法为O(m+n)。
接下来用尽量简洁的篇幅让你明白这个伟大的算法。
算法逻辑：
首先声明所有数组第一个下标从0开始。(有些教程会选择从1开始，先说清楚，以免搞混了)。
这里我们使用一个例子来简单说明一下
例如
如果我们用暴力寻找的话，那么过程是：
总共比对了 4 + 1 + 1 + 1 + 7 + 1 +1 + 1 + 3 + 1 + 1 + 8 +1 +1 +1 +8 = 41 (次)
如果改进成KMP的话，那么运算过程就是(灰色地方是KMP算法不去考虑的地方，红点是每次比较的字符串位置)
image.png
总共比对了 4 + 1 + 7 + 1 + 1 +8 + 4 = 26 (次)
如果我们看红点在abcxabcdabxabcdabcdabcy的位置，我们就会发现红点一直在向前移动，不会往后退/回头。这就是KMP算法的优点即不会倒退(也有人称作回溯)，所以就能避免不必要的匹配检查。
让我们依次看看KMP算法在上面的例子中都做了些什么。
首先让我们看一下第一个例子。
image.png
绿框中是KMP算法跳过的地方，那么我们就来对比一下两个红框里面的内容。
image.png
这里我们可以看到，深绿色方框那里是不相同字符的位置与新一轮判定的开始位置。
深橘黄色方框里的是已经匹配成功的字符串 abc。
关键的地方来了，因为已经匹配成功的字符串abc中没有相同的前后缀，所以下一次比对要从abcdabcy的首位开始比较。
我们简单地来看一下abc的前后缀情况。
要注意，这里我们看的前后缀的长度要小于已匹配到的字符串长度，因为如果长度一样了那就不用分前后缀了，也没有比较的意义了。
因为没有相同的前后缀，我们就不用担心错过什么，直接从配对失败的地方开始新的匹配就行了。
这个很好理解，让我们假设一下如果在上面这个例子中间有这么一种情况
在这里如果符匹配条件我们至少需要满足方框内的字符相同。
让我们看看方块内的字符处于abc中的什么位置
在黄色框内，bc属于abc的后缀，ab属于abc的前缀，所以如果条件符合的话，abc需要有相同的前后缀。
不理解为什么的同学不用担心，现在只要记住我们在寻找相同前后缀就行了，一会看完应该就能想通了。
让我们看看下一个例子。
在这个例子中KMP算法跳过了绿色方框的部分，直接运行了红色方框里的内容。让我们看看红色方框里发生了什么
深绿色方框位置是不相同字符位置与新一轮比较的位置。
深橘黄色方框里的是已经匹配的字符串 abcdab。
让我们来找一下 abcdab的前后缀吧。
我们发现abcdab有相同的前后缀。
重点又来了，如果有相同的前后缀，我们就需要把前缀移动到后缀的位置上。
这样abcdabcy就向右移动了四位，然后开始比较abcdabcy[相同前后缀长度] 上的字符，即第3个字符c(默认索引从0开始)。
不明白没有关系，我们再看两个例子。
在上面这个例子中，绿色依然是被忽略的部分，红色方框是KMP算法执行的部分。
让我们继续关注红色方框里的内容：
深绿色的地方是匹配到不一样字符的位置，也是下一次比较的开始位置。
深橘色的地方是已经成功匹配的字符串ab。
由于ab没有相同的前后缀，所以下一次比较从abcdabcy开始。
最后我们看看这个例子
依旧只看红色方框部分
深绿色的地方是匹配到不一样字符的位置，也是下一次比较的开始位置。
深橘色的地方是已经成功匹配的字符串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字符串
}
代码实现：
1. next数组
这里推荐一下个人觉得不错的视频，如果感兴趣的话可以深入了解一下https://www.bilibili.com/video/BV1Ys411d7yh?05:33，在5分33秒的时候开始讲解next数组的逻辑。（Ps：相信我，一遍可能看不懂，看三遍肯定会看懂了！！！）
整体的逻辑流程如图所示：
代码如下：
private int[] GetNext(string str){
int[] next = new int[str.Length];
next[0] = 0;
int i = 1;
int j = 0;
while(i < str.Length)
{
if (str[i] == str[j])
{
j++;
next[i] = j;
i++;
}
else
{
if (j == 0)
{
next[i] = 0;
i++;
}
else
{
j = next[j - 1];
}
}
}
return next;
}
2. KMP 算法的比较逻辑
然后我们再来梳理一下KMP算法取得next数组之后的逻辑。
很多人喜欢写做i，j。其实就是haystack与needle的下标，用hi 与 ni 来表示的话个人感觉会清晰一点。
代码可以写作：
private int KMP(string haystack, string needle)
{
int[] next = GetNext(needle);
int hi = 0;
int ni = 0;
while (hi < haystack.Length) {
if (haystack[hi] == needle[ni]) {
ni++;
hi++;
}
if (ni == needle.Length)
{
return hi - ni;
}
else if (hi < haystack.Length && haystack[hi] != needle[ni])
{
if (ni != 0)
ni = next[ni - 1];
else
hi++;
}
}
return -1;
}
接下来我们就可以写出KMP的主方法了。
private int KMP(string haystack, string needle)
{
int[] next = GetNext(needle);
int i = 0;
int j = 0;
while (i < haystack.Length) {
if (haystack[i] == needle[j]) {
j++;
i++;
}
if (j == needle.Length)
{
return i - j;
}
else if (i < haystack.Length && haystack[i] != needle[j])
{
if (j != 0)
j = next[j - 1];
else
i++;
}
}
return -1;
}
在运行KMP之前对输入参数进行一些简单的校验：
if (string.IsNullOrEmpty(needle))
{
return 0;
}
if (needle.Length > haystack.Length || string.IsNullOrEmpty(haystack))
{
return -1;
}
所以全部代码为：
public class Solution {
public int StrStr(string haystack, string needle)
{
if (string.IsNullOrEmpty(needle))
{
return 0;
}
if (needle.Length > haystack.Length || string.IsNullOrEmpty(haystack))
{
return -1;
}
return KMP(haystack,needle);
}
}
private int KMP(string haystack, string needle)
{
int[] next = GetNext(needle);
int i = 0;
int j = 0;
while (i < haystack.Length) {
if (haystack[i] == needle[j]) {
j++;
i++;
}
if (j == needle.Length)
{
return i - j;
}
else if (i < haystack.Length && haystack[i] != needle[j])
{
if (j != 0)
j = next[j - 1];
else
i++;
}
}
return -1;
}
private int[] GetNext(string str){
int[] next = new int[str.Length];
next[0] = 0;
int i = 1;
int j = 0;
while(i < str.Length)
{
if (str[i] == str[j])
{
j++;
next[i] = j;
i++;
}
else
{
if (j == 0)
{
next[i] = 0;
i++;
}
else
{
j = next[j - 1];
}
}
}
return next;
}
结语
感谢牛客大佬bailixi的讲解，本文主要是大佬在leetcode上的讲解并对其中错误地方进行了更正。如果在文中还有说错的地方或有疑惑的地方请留言告诉我，我看到了会尽快回复！希望帮助大家一起理解KMP算法，觉得不错的话也请点个赞，谢谢！！！！
这里附上大佬的讲解链接：
https://leetcode-cn.com/problems/implement-strstr/solution/c-kmp-xi-wang-wo-jiang-ming-bai-liao-kmpsuan-fa-by/
