大家好，我是讯享网，很高兴认识大家。

本篇文章适合被kmp折磨的头疼的小白，手把手带你走一遍，再多加体会就能懂了。

一、关于BF(暴力)算法的引入

bf算法即最朴素的的字符串匹配算法，也是最好理解的匹配算法但同时也是最费时的算法，别怀疑，就是一个字符一个字符比较。

关于bf不再多做赘述，时间复杂度从O(1)到O(m*n)不等。可见时间复杂度是非常不确定的，这就是为什么我们需要kmp算法

二、字符串的前后缀（必看）

在具体讲kmp算法前，必须引入一个概念：最长相同前后缀。

先给例子：请问abcmab的最长相同前后缀是什么？

我们先找出所有前缀和后缀

首先是前缀 {a,ab,abc,abcm,abcma} //最长前缀到最后一个字符的前一位

然后是后缀{b,ab,mab,cmab,bcmab}//最长后缀到最前一个字符的后一位

最后是最长相同前后缀 “ab”

就这样我们找到了这整个字符串的最长相同前后缀

建议：自己多尝试几组寻找几组最长前后缀（不自己找几组永远不会）

例如： ababa 的最长相同前后缀

前缀{a,ab,aba,abab}

后缀{a,ba,aba,baba}

所以可以看出来，最长相同前后缀是可以有公共部分的.(这是一个小坑，考试别踩了)

但是请注意：最长相同前后缀不是字符串本身，即 （ababa的最长公共前后缀是ababa）错！这样没有意义。

三、KMP算法

零、next数组的代码

求kmp算法的核心就是求next数组，至于求了之后有什么用我们再说。

直接上next数组代码，看不懂没关系，把注释看一下，然后记住有next这个数组就行。

typedef struct { char data[MaxSize]; int length;//串长 } SqString; ​ void GetNext(SqString t,int next[])//求next数组 { int j,k; j=0;k=-1;//k=-1其实是有原因的，下面会说明 next[0]=-1;//第一个字符前无字符串，给值-1 while (j<t.length-1)  //因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后 //所以最后一次经过while循环时j为t.length-2  //这段注释可看可不看，j最后总是会走到最后一个位置的，基础不好的不用太纠结。 { if (k==-1 || t.data[j]==t.data[k]) //k为-1或比较的字符相等时 { j++;k++; next[j]=k; //对应字符匹配情况下，s与t指向同步后移       }       else { k=next[k];//神来之笔，一般人确实看不懂。 } } }

讯享网

讯享网​

一、next数组是什么

首先我必须说明next数组是存什么的

next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。

即：每一个字符都有对应的next值

用例子说明：字符串abcabd

|a|b|c|a|b|d|

|0|1|2|3|4|5|

那么next[5]的含义就是“d”前面部分“abcab”的最长相等前后缀的长度

abcab最长前后缀是“ab” 所以next[5] = 2;

看懂这个例子后

这样我们就能直接求出字符串abcabd的next数组了

next[0] 对应a 即字符串的起头，由于这个位置位于头部，所以没有最长相同前后缀。

本来应该用0写入的,但是我们为了计算机的方便，我们永远固定next[0] = -1（这也是这个算法的精华之一，后面你就懂为什么了）

next[1] 对应b 该位置前面只有“a” 由于最长相等前后缀不能为它本身 所以next[1] = 0

next[2] 对应c 该位置前面为“ab” 无最长相同前后缀，next[2] = 0

next[3] 对应a 该位置前面为“abc" 无最长相同前后缀 next[3] = 0

next[4] 对应b 该位置前面为"abca" 最长相同前后缀为"a" next[4] = 1

next[5] = 2 (上面已求)。

至此，字符串abcabd的next数组我们已经全部求出来了

next[] = {-1,0,0,0,1,2}

可是问题是这是我们人求出来的，电脑该怎么求呢？

二、next数组代码解释

让我把算法拉下来

void GetNext(SqString t,int next[])

可以看到我们只传入了一个字符串和一个空的next数组。

这表示我们只用对模式串进行操作，而不用去操作主串。（主串是被匹配串，模式串是匹配串）

讯享网 int j,k; //j用来指字符串的位置，k用来给next数组赋值 j=0;k=-1; next[0]=-1;//0位置的字符对应的next值为-1

k=-1和next[0]=-1都是前置工作，千万别在这钻牛角尖，下面的代码学懂了你就知道了，然后你就会敬佩写出这个算法的大牛们。

重点来了，kmp的精华都在这个循环里

while (j<t.length-1)  { if (k==-1 || t.data[j]==t.data[k]) //k为-1或比较的字符相等时 { j++;k++; next[j]=k; //对应字符匹配情况下，s与t指向同步后移       }       else { k=next[k];//表示该处字符不匹配时应该回溯到的字符的下标，读不懂没关系，往下看。   } }

让我带你们模拟一遍就知道这个代码怎么走了。

讯享网

我们传入一个模式串 s[] = {aabaac}

然后我们跟着代码运行一次（绝对的适合小白）

讯享网//循环一 ​ j=0,k=-1 ​ //if通过，k==-1 ​ j++;k++ //j=1,k=0 ​ next[j]=k //next[1] = 0 对应a 位置1前面只有单字符a ​ //循环二 ​ j=1,k=0 ​ //if通过,s[1]==s[0] ​ j++;k++ //j=2,k=1 ​ next[j]=k //next[2] = 1 对应b的最长相同前缀 长度 为1，最长相同前缀为”a“ ​ //循环三 ​ j=2,k=1 ​ //if 不通过(s[2]!=s[1]&&k!=-1) ​ //要开始回溯了，注意看！ ​ k=next[k] // k=next[1]=0 ​ //循环四 ​ j=2,k=0 ​ //if不通过 (s[2]!=s[0]&&k!=-1) ​ k=next[k] // k=next[0]=-1 !!!k成功回到-1了，这就是这个代码神的地方 ​ //循环五 ​ j=2,k=-1 ​ //if通过 k==-1 ​ //略

这段代码最重要的是循环三四五，我们可以看到k是如何回到-1的

那句话怎么说来着，一切都是命运的安排（bushi，是大牛安排的，真的让人佩服

大家知道next[0]为什么要是-1了吗？

next[0]=-1确保了k的值最后会回到-1

而k=-1时循环得以继续，我们的“j"可以继续向后走

同时由于我们是在循环内部先 j++ ;k++ 然后next[j] = k;保证了j位置的next值是正确的。

（看不懂为什么保证正确的，在纸上自己做一遍也能懂）

是不是对这个算法刮目相看了，如果你还不懂，我强烈建议你一步一步在纸上走一遍，

其实不管懂还是不懂，在纸上自己走一遍都能对这个算法的理解大大加深，这也是我最后看懂了的原因。

三、next数组的用处

我们费了老大力气求出来了next数组，这有什么用呢？

当然是用来匹配字符串啦

我先丢出一个主串 ： abcabeabcabcmn

然后给出一个模式串：abcabcmn

直接开始匹配

第一次匹配

abmabe abcabcmn

abmabc mn

出现了不匹配的地方，怎么办？

我们只需要移动模式串就好了

第一次移动

abcabeabcabcmn

       abmabcmn

我们这次先不匹配，先看移动方式

即 最长相同前后缀的 前缀 移动到 后缀 位置上

那么具体是怎么移动的呢？答案就是我们的next数组了

由于在第一次匹配时（e与c不匹配）那么c位置的next数组就发挥作用了

由计算可知，next[c] = 2

所以我们模式串的指针直接等于next[c]=2 (j=next[j]=2)，这样就把前缀移动到后缀位置了

然后第二次匹配 （e与m不匹配）

模式串指针等于next[m] = 0 (j=next[j]=0)

第二次移动

abcabeabmabcmn

           abmabcmn

第三次匹配 (e与a不匹配)

模式串指针等于next[a] = -1 (j=next[j]=-1)。等于-1了，这怎么办呢？

别急，我们来看代码

int KMPIndex(SqString s,SqString t)  //KMP算法 { int next[MaxSize],i=0,j=0; GetNext(t,next); while (i<s.length && j<t.length)  { if (j==-1 || s.data[i]==t.data[j])  { i++;j++;  //i,j各增1 } else j=next[j]; //模式串指针等于next[]对应值 } if (j>=t.length) return(i-t.length);  //返回匹配模式串的首字符下标 else   return(-1);        //返回不匹配标志 }

可以看到 j==-1时主串和模式串都会自增，这样就可以继续匹配下一位了，所以可以看出kmp算法里-1的重要性了吧！

如果还不懂，一定一定要自己跟着我的代码用手写一遍。

最后是时间复杂度

KMP算法中多了一个求数组的过程，多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m)，因后面匹配中主串不回溯，比较次数可记为n，所以KMP算法的总时间复杂度为O(m+n)，空间复杂度记为O(m)。可以看出kmp算法比起暴力算法提速不止一点点。

写在最后

其实kmp真的没有那么复杂，就是怕你钻进牛角尖，比如你要去死想k为什么等于-1，只能说这是大牛们的天才想法，你我知道它的原理就行，自己动手写几遍，你也一定能搞懂，