在讲ＫＭＰ之前请允许我回顾一下ＢＦ算法，那么什么叫ＢＦ算法呢?就是最普通的暴力，请见下方的代码

 1 int return_pos(string S,string P) { 2     int i = 0,j = 0,k = 0; 3     int Slen = S.length(); 4     int Plen = P.length(); 5     while (i < Slen && j < Plen) { 6         if (S[i + k] == P[j]) { 7             ++k,++j; 8         } 9         else {10             i++,j = 0,k = 0;11         }12     }13     if (j == Plen) return i; 14     return -1;　// 返回-1表示不匹配15 }

通过上面的代码，估计你已经知道了什么叫做ＢＦ了吧；（在看不懂上面代码之前不要往下看，看了你也不懂，最好弄懂每个字母代表的含义，这是我没有加注释的原因之一，原因之二呢，实在是不想打注释。。。O(∩_∩)O哈哈~。。。）

好的，接下来就到我们的重点了，ＫＭＰ算法；

正如上面的ＢＦ算法所示，当每一次不匹配的时候，ｉ回到原来位置，然后ｉ＋＋，ｊ= 0;可以看出每一次的ｉ回到原来位置，ｊ 赋值为０，

是不是太麻烦了，如果串的长度太大，你懂得。。。。。

好了，ＫＭＰ这个时候来了，他们就想啊，如果我们不让ｉ回到原来位置（也就是说不要ｋ（ＢＦ中的）了），只让ｊ在动，能不能实现这个字符串匹配呢，

ｗｏｗ，最后他们成功了，（是时候该骂他们了，就是因为他们成功了，我们还要学这破算法，学就学吧，还ＴＭＤ那么难理解）

废话不说，请看下方。

那么我们来个例子，我们设Ｓ串ａｂａｂｃ，Ｐ串为ａｂｃ。好的，那么我们先看一下，ＢＦ是怎么实现的。。。。。

S       a(babc)     ab(abc)    aba(bc) 

P       a(bc)         ab(c)        abc　

（我擦。。。不匹配，白忙活了，看我回溯。。。）

S      ab(abc) 

P        a(bc)

（我擦来。。。还是不匹配，我再回溯。。。）

S       aba(bc)    abab(c)     ababc

P           a(bc)        ab(c)         abc

（要西，终于匹配了。）

接下来看ＫＭＰ是怎么做的

S       a(babc)     ab(abc)    aba(bc)  

P       a(bc)         ab(c)        abc　

（我擦。。。不匹配，白忙活了，看我ｎｅｘｔ。。。）

S       aba(bc)       abab(c)   ababc 

P           a(bc)           ab(c)       abc

 （牛逼吧。。。。。）

通过看这组样例，估计大家已经觉得ＫＭＰ的神奇之处了。（难道你不想问我ｎｅｘｔ是干么的吗？什么？你不问？那我也要跟你说，接着往下看。。。）

那么重点来了。下面解释一下啊ｎｅｘｔ数组的含义，这也是ＫＭＰ不太好理解的地方。

　　令原始串为Ｓ（是Ｓ，不是Ｐ）长度为ｎ，模式串为Ｔ（是Ｔ！是Ｔ！！）长度为ｍ；

　　我们假设目前匹配到如下位置

　　　　　　S0,S1,S2,S3,.....,Si-j,Si-j+1,...........Si-1,Si,Si+1,.......Sn

　　　　　　　　　　      　　  T0,T1,...............Tj-1,Tj,............

　　（绿色的部分为匹配部分，红色为不匹配的部分）估计你看出来了吧，恰好Si和Tj的时候，失配，那么我们将不会动i的位置。动用next神器。

        1）如果模式串右移1位（为了简单，就让我假设1位吧），即 next[j] == j - 1（对吧），好，那看看接下的KMP是怎么做的

　　　　　　S0,S1,S2,S3,.....,Si-j,Si-j+1,...........Si-1,Si,Si+1,.......Sn

　　　　　　　　　　　　        T0,T1,...............Tj-1,Tj,............

　　　　　　　　　　　　　　      T0,T1.................,Tj-1,Tj.............

　　　（蓝色的部分是即将要看看是否匹配的字符） 看到了吧，是不是省下了好多不必要的麻烦。

　　　（难道你没有问题要问我吗？什么？没有？真没有？你确定？那我问你一个问题，请看下方）

　　　　　　S1,S2,S3,.....,Si-j,Si-j+1,...........Si-1,Si,Si+1,.......Sn

　　　　　　　　　　　　　   T0,T1...........,Tj-2,Tj-1,Tj.............

　　　（好，请回答我，为什么绿色的部分是匹配的呢？什么？我说的，我什么时候说的？看到粉色的字符了吗？原来Si-j与T0匹配，哈哈，回答不出来吧，让我们

　　回想一下next的作用，为什么next[j] == j - 1,因为T0,T1......Tj - 2  ==  T1,T2........Tj - 1。。。。看到这个是不是你想到什么东西，对，就是老师上课讲的那个令人头痛的公式，没记错的的话，应该在PPT28页，你可以回去看看，现在应该可以看的懂了。）  

　　　通过这个例子，我现在就可以告诉你了，next[j] 就是记录T[0...j-1]中前缀和后缀相等的最大长度。

那么接下来，我就敲一遍KMP的核心算法。请看下方。。。

 1 void Get_next(string P,int* next) { 2     int i,j; 3     next[i = 0] = j = -1; 4     int len = P.length(); 5     while (i < len - 1) { 6         if (j == -1 || P[i] == P[j]) { 7             next[++i] = ++j; 8         } 9         else j = next[j];10     }11 }

代码给你了，估计你能看得懂吧。

那么我就做个总结吧。。。归根究底呢，KMP算法的本质便是：针对匹配的模式串的特点，判断它是否有重复的字符，从而找到它的前缀与后缀，进而求出相应的Next数组，最终根据Next数组而进行KMP匹配。接下来，进入第二部分nextval数组。

请见连接（http://www.cnblogs.com/xiaoshanshan/p/4082011.html ）；

ＫＭＰ（课下总结）