KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。 来自百度百科

我们之前在前面讲过BF算法其实就是，sub[ j ]在str[ i ]没有找到 j 回到最开头 i 回到第一个相等的下一个，假设这个主串的长度是M子串的长度是N,那这个算法的时间复杂度就是O(M * N)。那可不可以对我们的i 和 j 进行控制吗，让他动的不是那么频繁，降低时间复杂度。

让我们看以下例子

讯享网

在这块 i j 匹配失败了按照原来的BF,是不是我们的 j 就要退回到sub的开始，但是我们看i 的前面 已经又一段ab 和 j 中的一段是相等的了，毕竟j都跑到这块了肯定是有一部分是相等的，那既然有一部分相等那 i 可以就不移动了 ，j只要去一个特殊的地方就好了！对于这个例子我们的i就可以在这块。

j 既然走到后面说明不只是sub的前面有ab相等，后面这个ab也与str里面的ab相等，那我们就回退到这个相等的这段串，第一次结束的下一个位置（也就是回退到长度的值所在的下标）我们这里的j就在5号位置，他就回退到了2号位置。

那每个sub对应的下标都有一个回退的位置，那我们把这个数据采集起来，当要退回位置的时候通过你的 j 去操控不就好了吗？

next数组

这里我们就引入了next数组，这个数组就是保存每个sub对应下标的回退位置，那怎么去算呢？

回到刚才那个例子

 我们不是要找相同串的长度吗，那是哪一个串呢，是sub[ 0 ]开头 sub[ j - 1]结尾的两个相同的真子串（包括他自己），这个例子j在5的位置那个串就是ab。

我们规定在next数组的0号下标位置放 -1 （后面会讲为什么）

 我们的 j 动到下一个位置 没有相同的两个真子串那就是0。

 当 j  动到这块的时候是不是 我们要找到的是，sub[ 0 ]开头 sub[ j - 1]结尾的两个相同的真子串（包括他自己），打眼一看，哟这不是a吗，长度多少呢？ 1！这个数就是1了。

这个sub的next数组如下

我在随便给一串字符串，大家可以算一下他的next数组。

ababcabcdabcde       -1 0 0 1 2 0 1 2 0 0 1 2 0 0

为啥i不退回j退回这个相同真子串的位置的下一个？

 我们现在可以算出来next数组了但是我们怎么填满这个数组呢？不可能在计算机里面手算吧！

给出推导过程。

#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <string.h> void GetNext(const char* sub, int* next) { int subsize = strlen(sub); next[0] = -1; if (subsize == 1) { return; } next[1] = 0; int i = 2; int k = 0; //i自己加过一次了 while (i < subsize) { if ((k == -1) || sub[i - 1] == sub[k]) { next[i] = k + 1; i++; k++; } else { k = next[k]; } } } int KMP(const char* str,const char* sub, int pos) { assert(NULL != str); assert(NULL != sub); int subsize = strlen(sub); int strsize = strlen(str); int* next = (int*)malloc(subsize * sizeof(int)); assert(NULL != next); if (subsize == 0 || strsize == 0) { return -1; } if (pos < 0 || pos >= strsize) { return -1; } GetNext(sub, next); int i = pos; int j = 0; while (i < strsize && j < subsize) { if ((j == -1) || str[i] == sub[j]) { i++; j++; } else { j = next[j]; } } free(next); if (j >= subsize) { return i - j; } return -1; } int main() { printf("%d", KMP("aaaaabaaa", "b", 0)); }

next数组的优化nextval数组

我们再想想，如果前面很多很多都是相同的比如这个例子。

1.当回退到与当前字符一样的时候就写回退到的那个next值

2.如果回退到与当前字符不一样的时候就写当前这个next值

改进的KPM算法

讯享网#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <string.h> void GetNext(const char* sub, int* next) { int subsize = strlen(sub); next[0] = -1; if (subsize == 1) { return; } next[1] = 0; int i = 2; int k = 0; //i自己加过一次了 while (i < subsize) { if ((k == -1) || sub[i - 1] == sub[k]) { next[i] = k + 1; i++; k++; } else { k = next[k]; } } } void GetNextVal(const char* sub, int* next, int* nextval) { nextval[0] = -1; nextval[1] = 0; int subsize = strlen(sub); int i = 2; int k = next[i]; for (i = 2; i <= subsize; i++) { // 临时记录当前元素要回退的位置 int temp = next[i]; if (sub[temp] == sub[i]) { nextval[i] = nextval[temp]; } else { nextval[i] = temp; } } } int KMP(const char* str,const char* sub, int pos) { assert(NULL != str); assert(NULL != sub); int subsize = strlen(sub); int strsize = strlen(str); int* next = (int*)malloc(subsize * sizeof(int)); assert(NULL != next); int* nextval = (int*)malloc((subsize+1) * sizeof(int)); assert(NULL != nextval); if (subsize == 0 || strsize == 0) { return -1; } if (pos < 0 || pos >= strsize) { return -1; } GetNext(sub, next); GetNextVal(sub,next,nextval); int i = pos; int j = 0; while (i < strsize && j < subsize) { if ((j == -1) || str[i] == sub[j]) { i++; j++; } else { j = nextval[j]; } } free(next); free(nextval); if (j >= subsize) { return i - j; } return -1; } int main() { printf("%d", KMP("aaaaabaaa", "b", 0)); }

strstr的实现

#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <string.h> void GetNext(const char* sub, int* next) { int subsize = strlen(sub); next[0] = -1; if (subsize == 1) { return; } next[1] = 0; int i = 2; int k = 0; //i自己加过一次了 while (i < subsize) { if ((k == -1) || sub[i - 1] == sub[k]) { next[i] = k + 1; i++; k++; } else { k = next[k]; } } } void GetNextVal(const char* sub, int* next, int* nextval) { nextval[0] = -1; nextval[1] = 0; int subsize = strlen(sub); int i = 2; int k = next[i]; for (i = 2; i <= subsize; i++) { // 临时记录当前元素要回退的位置 int temp = next[i]; if (sub[temp] == sub[i]) { nextval[i] = nextval[temp]; } else { nextval[i] = temp; } } } const char* My_strstr(const char* str, const char* sub) { assert(NULL != str); assert(NULL != sub); int subsize = strlen(sub); int strsize = strlen(str); int* next = (int*)malloc(subsize * sizeof(int)); assert(NULL != next); int* nextval = (int*)malloc((subsize + 1) * sizeof(int)); assert(NULL != nextval); if (subsize == 0 || strsize == 0) { return NULL; } GetNext(sub, next); GetNextVal(sub, next, nextval); const char* i = str; int j = 0; int count = 0; while (count < strsize && j < subsize) { if ((j == -1) || *i == sub[j]) { i++; j++; count; } else { j = nextval[j]; } } free(next); free(nextval); if (j >= subsize) { return i - j; } return NULL; } int main() { printf("%s", My_strstr("aaaaabaaa", "b")); }