KMP算法C++代码

KMP算法的思想一般数据结构书都有讲，没讲的话google一下，有很多文章解释了其思想。晚上写了写这个代码，虽然不难，但还是费了番功夫调试，出现的主要问题有：无符号整型数据与整型数据比较大小（让我越来越讨厌无符号数！），还有一个问题就是KMP算法本身与求next数组的算法很类似，但是有些微妙的区别，也让调试了几次。

 

int *  GetNextVal( const   char   * s,  int   & len)
{
    len  =  strlen(s);
     int   * next  =   new   int [len];
     int  i  =   0 ;
     int  j  =   - 1 ;
    next[ 0 ]  =   - 1 ;
     while (i < len - 1 ) // 注意这里跟KMP函数里面的不同
    {
         if (j ==- 1   ||  s[i] == s[j])
        {
             ++ i;
             ++ j;
            next[i]  =  j;
        }
         else
        {
            j  =  next[j];
        }
    }
     return  next;
}

int  KMP( const   char   * s,  const   char   * t)
{
     int  slen,tlen;
     int  i,j;
     int   * next  =  GetNextVal(t, tlen);
    slen  =  strlen(s);
    i  =   0 ;
    j  =   0 ;
     while (i < slen  &&  j < tlen)
    {
         if (j ==- 1   ||  s[i] == t[j])
        {
             ++ i;
             ++ j;
        }
         else
        {
            j  =  next[j];
        }
    }

    delete[] next;

     if (j == tlen)
         return  i  -  tlen;
     return   - 1 ;
}

int  main( int  argc,  char   * argv[])
{
     char  s[ 128 ],t[ 128 ];
     while (cin >> s >> t)
    {
         int  pos1  =  KMP(s,t);
         int  pos2  =  strstr(s,t)  -  s;
        cout << pos1 << " : " << pos2 << endl;
    }
     return   0 ;
}