【原创】KMP算法代码（C）

//s是模式字符串，t是匹配字符串（可以看我上一篇文章中的叙述）
int KMP(const char * s , const char * t)
{
    int slen = strlen(s) , tlen = strlen(t);
    int i = 0 , j = 0;
    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 == 0)
            {
                 j = j + 1;//如果第一个字符都不匹配，就直接移一位
            }
            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-1];            
            }
    }
       free( next );
    if( i == slen )               //说明匹配成功
        return j - slen;        //返回目标字符串中匹配字符串的位置
    else
        return -1;                //表示匹配失败
}

首先是KMP算法的主体，可能存在一定的代码冗余，但是是完全按照我上篇文章所写的内容写的，可能和网上的代码不太一样，但更好理解。下面插入生成部分匹配值的函数。

void * GetNextVal( const char *s , int *temp )
{
    int i = 0 , j = 0;
 4
    temp[0] = 0;
    
    while( i < len)
    { 
        i++;
        if ( s[i] == s[j] )
        {
            j++;
            temp[i] = j;
        }
        else
        {
             j = 0;
             if ( s[i] == s[j] )
             {
                 j++;
                 temp[i] == j;
             }
             else
             {
                 temp[i] == j;
             }
        }
    }    
}

这个函数代码冗余量有点多，需要改进，但目前没有想到修改方法。