前言
KMP算法是为了字符串匹配问题而被研究出来的，字符串匹配问题就是查看一个字符串A是否是字符串B的子串，如果是字串的话，在B的哪个位置？此算法代码简练，但理解起来非常困难，建议挑出一整块时间来专门学习，本文作者写的非常用心，还不了解KMP的小伙伴一定要静下心来慢慢细品，你一定会有所收获🍊
一、字符串匹配问题
如果遇到这种在一个字符串中寻找另一个字符串的子串这种问题，大多数人第一时间想到的肯定是通过暴力匹配算法来完成，也就是Brute-Force算法简称BF算法，时间复杂度为O（m*n）,如果有上千行上万文本呢？，时间成本一定会很高，所以D.E.Knuth，J.H.Morris和V.R.Pratt三位大神提出了KMP算法，KMP（Knuth-Morris-Pratt ）算法也由他们三个的名字命名。
1.BF算法
2.KMP算法
肉眼可见的差距
二、next数组
next数组是KMP算法的精髓
KMP之所以会这样高效的查找字符串全都是next数组的功劳，也就是动图中字符串下面的数字，KMP算法会根据生成的next数组来移动，如果比对错误，将子串的首位直接移动到主串对比错误的位置，随后根据next数组提供的下标向左移动x格，图中下标为-1，所以向左移动-1格，就是向右移动一格
三、手写nex思想
注：上面图片的下标是按照nextVal生成的，next数组生成请看下面，nextVal是next的改进版，后面会讲到，我们先理解next数组生成原理
next数组的值计算的是从第n位开始前面字符串的最大公共前后缀的长度，不包括整个字符串本身，比如有这样一个字符串
从第一位向前看，没有字符，没法求，所有人为规定next[0]固定为-1（这里也有部分老师讲解第一位是0，其实思想都一样只不过是下标不一样而已，我们学的是思想不用在意这些），从第二位b向前看，也没有公共前后缀，next[2]为0，从第三位c向前看，也没有，next[3]为0，第四位a向前看，也没有next[4]为0，第五位b向前看，此时，最大公共前后缀为a，长度就是1,next[5]为1，从第六位向前看，最大公共前后缀为ab，长度为2，所以next[6]为2
四、机算next思想
比如一个字符串abcda，此时next数组的最大公共前后缀是1，那如果加个b呢，abcdab，此时最大公共前后缀是2，加个c呢，最大公共前后缀就变成3，经过大量数据观察，发现每次最大公共前后缀最多+1。
如果一个字符串abcdeffabcde，此时最大公共前后缀是3，如果在后面加一个g，这个字符串变成abcdffabcdg，最大公共前后缀直接就变成了0，也就是说每次最大公共前后缀可能直接减少到0。
如果增加一个字符的时候，发现新增加的字符与前缀后面的字母不相同了，就会进行减少，如下图所示，一次次进行查找，当前新的最大相同前后缀是什么，直到查找到位置。
这种方法未免有些麻烦，我们可以利用已有的条件进行优化，如果没有找到，直接找到其对应的next数组的值的字符串的下标，进行比对，如果成功，将找打他的next数组的值进行+1，就是next数组最新一位的值，如果找到最后，会找到字符串下标为0的位置，0位置的next数组值是-1，拿到-1的话数组会报错，这里写代码的时候不要忘记处理。
为什么可以这么做呢？因为前面红框的前缀，等于后面红框的后缀，我们在此基础上向后进行对比一位即可判断出next数组最新一位的值。
五、next数组细节理解
为什么按照next数组移动就可以保证不跳过匹配成功的字符串呢？
前面说过，如果匹配失败子串的首字符的位置会移动到匹配失败的位置，再向左移动next数组[i]格，匹配失败的那一位的next数组记录着前面字符的最大公共前后缀长度，由于前面的前缀都已经于主串匹配过了，只不过后缀后面的位置对不上，那么我们直接将后缀的起始位置对准匹配失败的位置，也就是向左移动next[i]个长度（也就是向左移动最大公共前后缀的长度），就能保证跳跃过程中没有错过任何可以匹配成功的串。还可以使主串中已经成功配对的后缀于子串的前缀相匹配，再向后匹配。
下图中，①=②=③=④，所以移动回去时保证前面的后缀会与匹配失误的地方对齐
上面展示的是有公共前后缀的情况，那么如果整个字符串都没有公共前后缀会怎么样？
- 将发挥KMP算法的最大作用！
我们只需大胆向后跳，不用再往前跳了
此动画后半部省略掉了，找到最后没有发现相同串
六、nextVal数组
讲完了next数组，接下来讲解nextval数组，nextVal数组是next数组的改进版，因为next数组还有改进的空间，那就是在生成数组的时候对在next数组的基础上，对失配字符的next数组下标进行读取，读取数组下标到字符串的下标位置，然后进行比较，如果不相等，那么不对其进行优化，如果读取失配字符的next数组下标到字符串的下标位置相等，那么将读取失配字符的next数组下标到字符串下标，然后取出这个位置的next数组的值到失配位置的next数组。（这里难理解，多看几次）
这样做的原理是什么呢？
如果此时a在与上面的字符串进行配对，那么a此时与b失配，说明对比的数是非a，按照next数组原理我们将下标为0的位置移动到上面b的位置，可是a已经和b对比过了，将下标为0的a移动过去必然也会失配，所有nextVal要先对失配的位置与next数组的值对应的下标的字符进行比较，相等就会读取其对应位置的next下标到失配位置的next下标。
七、KMP算法代码实现
讲完了原理，这里是代码实现。文章来源：https://www.toymoban.com/news/detail-766244.html
- 可以将里面的next替换为nextVal，两者都为独立的数组生成函数。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
void getNext(int * next,const char* s,int len)
{
assert(next && s); //判断两个指针是不是空指针
int i = 0, cur = -1; //i是当前位置、cur是当前最大相同前后缀的长度
next[0] = cur;
while (i < len)
{
if (cur==-1||s[i]==s[cur]) //cur为-1的时候也要恢复成0同时i++
{
next[i + 1] = cur+1;
cur++; //cur恢复成0
i++;
}
else
{
cur = next[cur]; //如果失配，直接找到这个位置的next数组的值给到cur
}
}
}
int kmp(const char* p, const char* s)
{
int len = strlen(s);
int* next = (int*)malloc(sizeof(len) * len);
getNext(next, s, len - 1);
assert(next);
int i = 0, j = 0; //定义i为字符串下标，j为next数组下标
while (p[i])
{
if (j==-1||p[i] == s[j]) //如果next数组下标为-1，next数组下标恢复为0，字符串下标+1
{
i++;
j++;
if (s[j] == '\0') //如果字符串下标为‘\0’,查找成功返回i-j也就是字符串匹配成功位置的收个字符的下标
{
free(next);
next = NULL;
return i - j;
}
}
else
{
j = next[j]; //将此位置的next数组下标对准字符串对应位置得下标
}
}
free(next);
next = NULL;
return -1; //如果p[字符串下标]=='\0'，跳出循环，证明查找失败，返回-1
}
int main()
{
char p[] = "abcdabecabcfdsafdasdasfdasfasdfasfdasafdsbc";
char s[] = "abecab";
printf("%d", kmp(p, s));
}
八、nextVal数组代码实现
void getNextVal(int *next,const char* s,int len)
{
assert(next);
int i = 0, cur = -1;
next[0] = cur;
while(i < len)
{
if (cur == -1 || s[i] == s[cur]) //为-1注意处理
{
i++;
cur++;
if (s[i] != s[cur]) //比next数组增加一个判断
{
next[i] = cur;
}
else
{
next[i] = next[cur]; //如果相等，把next[cur]的值取过来
}
}
else
{
cur = next[cur];
}
}
}
完结
作者的话
KMP是一块硬骨头，建议各位能挑出一段长时间专门攻克它，不要今天看一点，明天再看一点，这样不会有收获，写代码不代表就已经真正理解了KMP，你最好要能熟练的讲给其他小伙伴KMP到底一种什么样的算法，记录一份详细的笔记，忘记的时候拿出来反复重温，最后如果觉得哪里没有理解，可以评论区留言或者私信作者，我会耐心地给大家来答疑解惑。当然如果有不足的地方还请各位帮忙补充。文章来源地址https://www.toymoban.com/news/detail-766244.html
到了这里，关于KMP算法细节详解（带动图理解）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
