首先要感谢http://blog.csdn.net/v_july_v/article/details/7041827以及http://blog.chinaunix.net/uid-27164517-id-3280128.html两篇博文的作者，参考这两篇博文才对KMP算法有了初步认识，本文的一些内容也是来自于这两篇之中。KMP算法与BF算法的优略、回溯不回溯这些问题本文不作说明，而主要说明next函数（通常保存为一个next数组）的意义。这正是KMP算法难于理解的地方。
为了方便起见，在不会起歧义的情况下做如下约定：下标都从0开始; 假设字符串为S，那么Si 表示第i个字符或者只有第i个字符的字符串；SiSi+1Si+2表示子串，如S1S2S3，S4S5等等；pre(S,i)表示字符串S的位置i之前的字符串，即S0S1...Si-1；next函数和next数组表示同一个意思。本文分为两节，第一节讲next函数的意义，得出需要满足的两个条件；第二节是具体代码以及相关说明。
第一节 next函数的意义
我们知道，KMP的基本匹配过程如下：在字符串T中查找模式P，需要记录T中的当前位置i 以及P中的当前位置 j。当Ti=Pj的时候i和j都自增；当Ti!=Pj时，令j=next(j)，然后继续匹配。这样就跳过了一些字符，而这些字符，本质上来讲与字符串P0P1...Pj-1的前缀和后缀能匹配的最大长度相关。以图一作解释，来倒推next(j)的意义：
图 1
在T中查找P，P0P1P2P3P4=T1T2T3T4T5，但P5!=T6（i=6,j=5）。此时令j=next(j)。假设next[5]=2, 则跳过三个字符，新的j=2，从这个位置开始比较。能跳过的条件是什么？其一，从虚线部分可知必须保证P0P1=P3P4；其二，P5不能等于P2，因为之前我们知道了P5!=T6，如果P5=P2，那么P2肯定不等于T6。再次强调观察虚线部分，发现P0P1和P3P4正好是字符P5前面的字符串（即P0P1P2P3P4）的前缀和后缀。
图1中，P5！=T6时跳过了三个字符，next[5]=2。再看图2：next(5)分别等于4,3,1,0的情况。
图 2
仔细观察图2中的四种情况，均需要符合上面所说的条件。对于图2的最后一幅图，此种情况的条件是P0P1P2P3P4没有相等的前缀和后缀，且P0!=P5。那么如果后一个条件不满足呢，那么显然P应该再移一个位置，对应的情况如图3：
图 3
图3中，next(5)=-1。因此next=-1的情况：Pj=P0，且P0P1...Pj-1没有任何相等的前缀和后缀。另外，一般地，如果P0就发生失配，那么显然i也要加一，因此next(0)=-1。
在此作一小结，k=next(j)需要满足的两个条件如下：
条件1. k是P0P1...Pj-1最长匹配的前缀和后缀的长度.
条件2. Pj!=Pk.
第二节 next函数的求法
利用以上知识，我们就知道求next函数的思路了。基本思路是利用上面的第一个条件（寻找最长匹配的前后缀），而第二个条件（Pj!=Pnext(j)）则作为优化。这样一步步理解会对算法思路更清晰一点。
基本思路: 利用条件1
使用归纳法:假设next(j)=k，则P0P1...Pk-1=Pj-k...Pj-2Pj-1，那么next(j+1)有两种情况:
1. 如果Pk=Pj，则P0P1...Pk=Pj-k...Pj-1Pj，所以next(j+1)=k+1=next(j)+1。
2. 如果Pk!=Pj，这是可以看做另外一个字符串匹配的问题，主串和模式串都是p，当匹配失败时，k=next(k)。
因此得到如下算法：
void
get_nextval(char
const* ptrn, int
plen, int* nextval)
{ int
i = 0;
nextval[i] = -1;
int
j = -1;
while( i < plen-1 )
{
if( j == -1 || ptrn[i] == ptrn[j] ) //对应情况1
{
++i;
++j;
next(i)=j;
}
else
//对应情况2
j = nextval[j];
}
} |
上述算法中，ptrn是模式串，plen是模式串长度，nextval数组保存所有位置的next值。该算法不考虑条件2，因此有可能发生Pi=Pnext(i)这种情况。在缺少该条件的情况下也可以用于做字符串匹配。假设next(i)=k，当匹配到i失效时，i=next(i)=k，这时候肯定也失效，因此又寻找k对应的next值，这样算法得以进行。
优化：利用条件2
比较常见的算法对情况1做了优化，如下:
1 void get_nextval(char const* ptrn, int plen, int* nextval) 2 { 3 int i = 0; 4 nextval[i] = -1; 5 int j = -1; 6 while( i < plen-1 ) 7 { 8 if( j == -1 || ptrn[i] == ptrn[j] ) //对应情况1 9 { 10 ++i; 11 ++j; 12 if( ptrn[i] != ptrn[j] ) 13 nextval[i] = j; 14 else 15 nextval[i] = nextval[j]; 16 } 17 else //对应情况2 18 j = nextval[j]; 19 } 20 }
该版本的算法考虑了条件2，因此进入情况1的时候，next(i)!=j。我们可以考虑一条查询链，如图4：
图4
假设现在刚刚运行完13行，得出next[i]=j。此时必然有ptrn[i]!=ptrn[j]。因此下个循环的时候会跳转到18行。该next链一直往前搜寻，直到某个位置k，ptrn[k]与ptrn[i]相等。该k就是最新的j值，这样回到情况1，接着按照条件1优化。另外，当j==-1也应当进入情况1，因为不能往前搜寻了。
以上就是next数组的求解过程，往后就可以利用next数组进行字符串查找了。在写查找算法的过程中，可以发现与求next数组的算法过程惊人的一致。这也是KMP算法的一个特点，把两者结合起来，更能够理解它的奥妙所在。