>> KMP算法详解，小白都懂的讲解，欢迎交流，边听歌边看吧
无羁MV 演唱：肖战，王一博_腾讯视频
概念解释
Knuth-Morris-Pratt算法，简称KMP算法，是一种字符串匹配算法。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。
Donald Knuth
KMP几年前学过，当时学的也忘得差不多了，到了今天，又接触到KMP，于是决定以最通俗形象的描述来讲解一下KMP。
字符串匹配
有一个主字符串S，长度为n ，和模式串P，长度为k，k>0并且k<=n，我们需要在主串S中找出第一个P（这里说第一个P是比较严谨的，因为有可能S中有多个P，我们只要找到第一个即可），并输出P在S中的第几位。
比如主串S为ABCABCABD，模式串P为ABCABD，那么我们应该应该输出3（序号是从0开始的）
序号：0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S： A｜B｜C｜A｜B｜C｜A｜B｜D
P： A｜B｜C｜A | B | D
常规思路-暴力匹配
在讲KMP之前，先按照正常思路来解，要想找到P，我们最容易想到的算法就是从左到右依次遍历主串S，依次和模式串P比较，直到找到完全匹配P的为止。
也就是说，我们先假设P在S的第i位，(i>=0，并且i <= n-k，这个范围懂不？因为如果n-i<k，那么肯定和P是不匹配的，长度都不对，怎么匹配呢)。即S[i] == P[0] , S[i+1] == P[1] , ... , S[i+k] == P[k], 所以我们先假设i为0，然后开始比较，如果匹配失败，则i++；直到找到完全和P匹配的，则输出i，如果i>n-k，则表示S中不存在P，输出-1.
下面实例形象说明，有两个数组，S和P
i = 0;
S序号 0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S： A｜B｜C｜A｜B｜C｜A｜B｜D
P： A｜B｜C｜A | B | D
P序号 0｜1 ｜2｜3 | 4 | 5
1、S[0] == P[0] ?，相等
2、继续比较S[1]==P[1] ?，依然相等
。。。（省略2、3、4的比较）。。。
3、继续比较S[5]==P[5] ?，结果不相等
上面我们是从S[0]开始和P[0]比较的，并且比较失败，这时候我们要尝试P[0]和S[1]比较
也就是 i=1;
序号：0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S： A｜B｜C｜A｜B｜C｜A｜B｜D
P： A｜B｜C｜A | B | D
P序号 0｜1 ｜2｜3 | 4 | 5
1、S[1] == P[0] ? A和B显然不等，匹配失败
那么我们S的指针继续指向下一个，P[0]和S[2]比较，即i=2；发现还是不等，相同的操作就不多说了，直接跳到 i=3；
序号：0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S： A｜B｜C｜A｜B｜C｜A｜B｜D
P： A｜B｜C｜A | B | D
P序号 0｜1 ｜2｜3 | 4 | 5
我们发现S[3]=P[0], S[4]=P[1],S[5]=P[2], S[6]=P[3]， S[7]=P[4]， S[8]=P[5]，匹配成功，输出3，结束。
下面看代码
//暴力匹配
void BF(char*S, char*P) {
unsigned long sLen = strlen(S); //S的长度
unsigned long pLen = strlen(P); //P的长度
int position = -1; //匹配的位置，默认是-1
int i =0, j =0;
while(i <= sLen - pLen) {
while(j < pLen) {
if(P[j] == S[i + j]) { //如果相等，则继续比较下一位
j++;
}else{
i++; //如果不等则从下一位开始比较
j =0;
break;
}
if(j == pLen) {
position = i; //如果j == pLen，说明匹配完了并且都对了，也就是找到了
}
}
if(position > -1) { //说明已经找到了
break;
}
}
printf("P at %d\n",position);
}
KMP登场
暴力匹配既然可以解决匹配问题，而且还简单，为什么需要KMP呢？显然，是为了优化，暴力匹配的时间复杂度是O(n*n)，优化空间还是有的。
还是刚才的例子，我们一起来看看哪里可以优化。
S序号 0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S： A｜B｜C｜A｜B｜C｜A｜B｜D
P： A｜B｜C｜A | B | D
P序号 0｜1 ｜2｜3 | 4 | 5
当我们比较到S[5] 和P[5]的时候，按照暴力匹配算法，下一步是i=1，也就是S[1]和P[0]比较，但是我们真的有必要把S[1]和P[0]比较吗？
我们给模式串来个特写 A｜B｜C｜A | B | D
发现了这个串有个特点，就是有两个AB，如果当D匹配失败的时候，说明主串前两个必定是AB，要不也不需要再和D匹配了。既然主串前两个是AB，而且模式串第一个字母和第二个字母也刚好是AB，那么就无需再重复比较了。细品这两句话，多读几遍，懂了再往下看。
懂了之后，我们再继续往下看，
那么i还有必要为1吗？没必要了，i可以直接保留为5，而j=2 ( j 为P的下标 ) , 因为我们知道S[3]S[4]为AB，P[0]P[1]也是AB，所以可以直接把S[5]和P[2]比较。
S序号 0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S： A｜B｜C｜A｜B｜C｜A | B｜D
P： A｜B｜C｜A | B | D
P序号 0｜1 ｜2｜3 | 4 | 5
由此我们可以看出，KMP的特定有
1、i不需要回退，（对比暴力算法，i每次匹配失败都要回退到原来的起点+1）
2、j不一定要重0开始，只是不一定
这样就省了不少时间。
那么问题来了，当我们遇到不匹配的字符的时候，我们如何确定模式串应该回退到哪？
这就是KMP里的重点了。
next数组
在KMP中，有个next数组，它的长度和模式串的长度一样，记录着对应字符匹配失败时应该回退到哪一个。
在求next数组前，先了解一个概念，叫前缀后缀最长公共元素长度。
前缀：字符串前面的子串，但不包含最后一个字符。比如字符串abcd，前缀有 a, ab,abc
后缀：字符串后面的子串，但不包含第一个字符。比如字符串abcd，后缀有 d,cd,bcd
前缀后缀最长公共元素：一个字符串中的所有前缀和后缀中，相同且最长的一个，比如abcd中，不存在前缀后缀最长公共元素。abcdabc中前缀后缀最长公共元素是abc。ababa的是aba。
为啥要介绍这个概念呢？因为next数组里面的值，就是当前字符之前的字符串中的最长相同前缀后缀长度。
P： A｜B｜C｜A | B | D
next: 0 | 0 | 0 | 0 | 1 | 2
模式串ABCABD对应的next数组就是000012；
这个next数组的值为什么是当前字符之前的字符串中的最长相同前缀后缀长度呢？对应下面的表格一起看，next数组本质是记录当前字符匹配失败时应该回退的位置，当第一个A匹配失败时，显然只能回退到自己本身，当B匹配失败，前面并无公共元素，所以也是回退到0，CA同理，当第二个B匹配时候时，因为前面有公共元素A，所以A不需要再比较了，回退到第一个B的位置也就是1，后面的同理。
下面表格表示每个字符位置对应的最长前后缀公共元素长度计算过程，粗体表示前后缀公共元素。
talk is cheap, show me the code，下面直接看看代码是如何实现这个过程的
//求next数组，next数组表示回退的值，而不是最大长度，若是把next数组整体左移一位，则表示最大长度了
void initNext(char*P, int*next) {
unsigned long pLen =strlen(P);//P的长度
//前两个肯定没有除了本身之外的公共元素，所以直接给0
if(pLen >0) {
next[0] =0;
}
if(pLen >1) {
next[1] =0;
}
intj =1;//P[j]表示后缀
inti =0;//P[i]表示前缀
while(j < pLen) {
if(P[j] == P[i]) {//如果后缀和前缀相等
j++;//则都加一，继续比较下一位
i++;
next[j] = next[j-1] + 1;//这里的j是加1之后的，所以下一个next的值是前面字符串的前后缀的最长公共元素长度，这里有点递进的感觉，前面的长度+1是因为又找到了一个相等的前后缀
}else if(i ==0){//如果前缀已经是0，则找下一个后缀
j ++;
}else {//如果匹配失败，则回退
i = next[i];
}
}
return;
}
这段代码可能比较难理解，其实是利用了递进关系，首先，需要注意，next是回退的位置，而不是最长的长度，也可以理解为最长长度减一，其实就差了一个1。next[0] 和 next[1]肯定是0，因为next[0]只有一个字符，不存在前后缀，也就是说，一旦P[0]匹配失败了，那也只能回退到P[0]，所以是0。next[1]为什么也是0? 从匹配的角度来解释，假设P[1]匹配失败，也只能向后回退，后面只有P[0]了。从前后缀的角度来解释，因为next[1]只有两个字符，那么前缀就是P[0]，后缀是P[1]，最大长度要么是1，要么是0，那么回退位置是最大长度减一，那么就是0或-1，不能为负数（数组下标没有负数），所以只能是0。
那么从next[2]之后的值，都存在一个关系，那就是
如果匹配到了一个相等的相等的前后缀，那么next[j] = next[j-1] + 1。
栗子：
index: 0 | 1 | 2 | 3 | 4 | 5
P： A｜B｜C｜A | B | D
next: 0 | 0 | 0 | 0 | 0 | 0
1、初始化所有的next为0
2、先比较最短的子串 AB （P[0]和P[1]）
3、AB不等，则比较AC（P[0]和P[2]）
4、AC不等，则比较AA，（P[0]和P[3]）
5、AA相等，则next[4] = next[3] + 1 ，也就是next[4] = 1;
index: 0 | 1 | 2 | 3 | 4 | 5
P： A｜B｜C｜A | B | D
next: 0 | 0 | 0 | 0 | 1 | 0
6、比较B和B（ P[1]和P[4]）
7、BB 相等，则next[5] = next[4] + 1 ，也就是next[5] = 2;
index: 0 | 1 | 2 | 3 | 4 | 5
P： A｜B｜C｜A |B |D
next: 0 | 0 | 0 | 0 | 1 | 2
8、比较C和D（ P[2]和P[5]）
9、CD不等，结束
KMP算法
next数组已经求出来了，接下来就可以写KMP算法了
主要思路就是 1、主串S开始遍历和模式串P比较 2、如果遇到匹配失败，则模式串回退到next[j]位置 3、如果遇到不匹配并且模式串本身就在0位置，则主串往下移动一位
代码就是
//KMP
void KMP(char*S, char*P) {
unsigned long pLen =strlen(P);
unsigned long sLen =strlen(S);
int*next = (int*)malloc(pLen *sizeof(int));
initNext(P, next);
inti =0;//主串的下标
intj =0;//模式串下标
int position = -1;
while(i <= sLen - pLen + j ) {
if(S[i] == P[j]) {
if(j == pLen -1) {//如果P已经匹配结束了，则表示找到了
position = i - j;//计算出第一个匹配的位置
break;
}
//右移一位比较
i++;
j++;
}elseif(j ==0) {
i++;//模式串是0，则只需移动主串
}else{
j = next[j];//回退
}
}
printf("KMP: P at %d\n",position);
}
其实求next的算法和KMP的算法是不是很像
网友评论