//s是模式字符串，t是匹配字符串（可以看我上一篇文章中的叙述）
int KMP(const char * s , const char * t)
{
int slen = strlen(s) , tlen = strlen(t);
int i = , j = ;
int *next = ( int * )malloc( sizeof( int ) * slen );
GetNextVal( s , next); //生成部分匹配值的函数
while( i < slen && j < tlen )
{
if(s[i] == t[j])
{
i++;
j++;
}
else
if(i == )
{
j = j + ;//如果第一个字符都不匹配，就直接移一位
}
else
{
//按照上一篇文章中写的，移动步数 = 已匹配字符 - 匹配值
//算式应该是：j = ( j - i )+ ( i - next[i-1] ) ;(j - i )为首字符所在的位置
//化简后为：j = j - next[i-1]; 再将匹配字符串的索引归0; i = 0;
//但我们发现，对于之前已经匹配的字符我们又重新比较了一次，
//所以进行修正，j的值不变，移动匹配字符串，即 i = next[i-1]; i = next[i-];
}
}
free( next );
if( i == slen ) //说明匹配成功
return j - slen; //返回目标字符串中匹配字符串的位置
else
return -; //表示匹配失败
}
首先是KMP算法的主体，可能存在一定的代码冗余，但是是完全按照我上篇文章所写的内容写的，可能和网上的代码不太一样，但更好理解。下面插入生成部分匹配值的函数。
void * GetNextVal( const char *s , int *temp )
{
int i = , j = ;
4
temp[] = ; while( i < len)
{
i++;
if ( s[i] == s[j] )
{
j++;
temp[i] = j;
}
else
{
j = ;
if ( s[i] == s[j] )
{
j++;
temp[i] == j;
}
else
{
temp[i] == j;
}
}
}
}
这个函数代码冗余量有点多，需要改进，但目前没有想到修改方法。