本着对KMP算法的好奇，特地进行学习一下。
@[toc]
一、简介
KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt三位科学家发表的一个模式匹配的算法，这种算法相较于BF（暴力）匹配算法可以大大减少其回溯计算的次数，也就是减少不必要的回溯发生。
该算法的核心是要构建一个引导整个匹配过程的next数组，我们可以把这个next数组看做是KMP算法中的回溯控制中心，它会控制匹配过程字符串T的回溯位置。具体的构建过程可以参看《大话数据结构》一书、与视频【C语言描述】《数据结构和算法》。
二、构建next数组
构建next数组的关键在于：找到当前字符之前的串的前后缀相同字符的个数。刚一开始有些难以理解这是什么意思，不过看一下代码应该就会好很多。如下所示：
#include<stdio.h>
typedef char* String;
//获取KMP算法所使用的next数组
void get_next( String T,int *next)
{
int i=1,j=0,len;
next[1]=0;
len=T[0] - '0';
while( i < len)
{
if(0 == j || T[i] == T[j])
{
i++;
j++;
next[i]=j;
/*if( T[i]!=T[j]) //优化
{
next[i]=j;
}
else
{
next[i]=next[j];
}*/
}
else
{
j=next[j]; //要回溯到next[j]位置
}
}
}
不难看出， 这里的前缀是指：字符串从第一个位置开始的前
-1（
）个字符，而后缀则是指字符串从当前位置开始的后
三、KMP算法的实现
//返回符合条件的字符串的位置
int Index_KMP( String S, String T, int pos)
{
int i=pos,j=1;
int next[255];
int sLen,tLen;
get_next(T,next);
sLen=S[0]-'0';
tLen=T[0]-'0';
while( i <= sLen && j <= tLen) //其中一个字符串达到末尾则终止匹配过程
{
if( 0==j || S[i] == T[j] )
{
i++;
j++;
}
else
{
j=next[j];
}
}
if( j > tLen )
{
return i-tLen;
}
else
{
return 0;
}
}
int main()
{
String S="5abcdex";
String T="2cd";
int pos=Index_KMP(S,T,0);
printf("%d\n",pos);
return 0;
}
执行效果：
参考资料：《大话数据结构》、【C语言描述】《数据结构和算法》
