在数据结构算法中，KMP算法可以说是为串的查找提供了良好的简约型方案，其最大的特点是主串的查找位置不需要回溯，有效地优化减少了查找的时间复杂度。具体详解可见http://baike.baidu.com/link?url=Z8lDiDx_z_3Z70Xc5n6avwOMHJJQDeBR20HlSAlN-YQI-sOc198b-9a6O_uBnPgZKTtAtS132VYJVBqFPwNgFK
此方法的主要依赖于对模式串的处理，在模式串的查找中，需要在每次匹配失败后，都需要判断出下一次查找的起始位置；对此判断过程可以经过一个新的函数来实现，下一次的查找地址用next[]来记录，在对next进行赋值的过程中，用程序的实现如图所示
其中，i代表当前与主串相比较的位置，j所代表的是从下标为一处开始与正在比较位置之前的元素相同的字串的长度，next则是失败后模式串所要重新与主串参与匹配当前位置所指元素进行匹配的位置；个人认为此算法可以由先比后加的思路简单理解。
先进行比较，再对加一的位置进行赋值，具体表现为首先判断当前主串所比较的元素之模式串当前比较的元素比较，如果成功匹配，则可分别将当前与主串匹配位置与模式串中子串位置分别加一后将next[j]的值赋予next[i]，如图，设i的位置为5，j的位置设为2，此后若6位置的a匹配失败后，由于12与45相同，则回溯位置为3即可，满足的公式正好为next[5+1]=next[2+1]，比较位置的结果决定之后一个位置对应next的下标，这正是i++,j++的巧妙之处。
在了解了这些之后，代码的编写就会容易许多，下面着重分析怎样对代码进行编写。
首先，需要考虑的是两种情况，即成功匹配和不成功匹配。不成功匹配中，又可以区分为：下一次的查找地址是1，即串首和非串首的串，在第二种情况下，必须满足的条件是在此次查找的前方必须有一个长度大于0的串与从第一个元素开始，与之等长且元素相同的串，可相交不可重合。拿上图举例，i=5时发生失配，其前面长度为1的串（下标为4）与第从头开始第一个元素（下标为1，可以理解为一个长度为1的串）相等，下一次的查找地址就是0+1。
在程序的编写中，首先考虑匹配成功，从第一次匹配开始，可以如此编写：
i=1;
if(j==0) {i++;j++;next[i]=j;} //为第一次比较，决定的是next[2]=1;
接下来，假设仍可以正确匹配，则有
if (ch[2]==ch[1]) {2+1;1+1;next[3]=2} //参考字串aaaaa
如果不是从确定第一个元素，如串：abaaaa,有
lf (ch[3]==ch[1]) {3+1;1+1;next[4]=2;} //第四个a匹配失败时的重新查找地址是2，满足上面的代码格式。
依次类推，可以将前后的查找方位用i,j代替，并且写入while语句中，情况如下：
while (i<length){
if (j==0||ch[i]==ch[j]) {i++;j++;next[i]=j;}
}
接下来考虑匹配失败时的情况，在此时，首先需要明白的是，next代表的含义，设next[i]的值是k;则表明在i的前面有k-1长度的串与从1开始k-1个串的长度相等。
接下来，需要注意的是，如果当前匹配成功，而下一个i+1;j+1;的字符匹配不成功，则需要重新匹配的位置是在i+1之前的n个可以与j之前n个完全匹配的
字符串，重新匹配的下标为n+1，n不小于0。此时，可以和上面一段话对比，发现在不成功匹配时，可以用一个关于next[]的函数循环实现。由于当前匹配成功时，已经进行过了i++，j++的过程，j与i对比出错后，重新与i对比以便于确定next[i+1]的值的j应该取next[j]，此过程需要保持i的值不变，因此，便可以在已有函数中加上匹配不成功的处理过程，结果如下:
while (i<length){
if (j==0||ch[i]==ch[j]) {i++;j++;next[i]=j;}
else
j=next[j];
}
需要额外考虑的是：如果n的值是0，即j=1与i-1的值仍旧不匹配，n=0；这种情况需要事先进行声明，有next[1]=0;此时正好进行j从0开始的匹配判断。
另外，由于是从第一个字符比较开始的，i的初始化值为1，此时j=0，正好进行第一次比较。
KMP算法的总结则如下：
next[1]=0;i=1;j=0;
while (i<length){
if (j==0||ch[i]==ch[j]) {i++;j++;next[i]=j;}
else
j=next[j];
}
文笔较渣，希望表达得可以理解。O(∩_∩)O
网友评论