KMP算法实现

[c]代码库

void get_nextval(char s[],int nextval[])//求模式串S的nextval函数值并存入到nextval[]中
{
   int i=0,j=-1;
   nextval[0]=-1;
   while(i<strlen(s))
  {
     if(j==-1||s[i]==s[j])
     {
      ++i;  ++j;
     if(s[i]!=s[j])
       nextval[i]=j;
      else
       nextval[i]=nextval[j];
     }
  else
    j=nextval[j];
  }
}

int KMP(char s[],char t[],int nextval[])//利用模式串t的nextval函数求t的主串s
{
   int ls=strlen(s);
   int lt=strlen(t);
   int i=0,j=0,len=0;

   while(i<=ls&&j<=lt)
   {
     if(j==-1||s[i]==t[j])//继续比较后继字符
      {  ++i;  ++j; }
     else
      j=nextval[j]; //  模式串向右移动
     if(j==lt)//通过nextval[]求得的j如果和模式串的长度相等就说明模式串在主串中出现了；
     {
      len++;
      j=nextval[j];
     }
   }
   return len;
}