Code666 (代码贴、代码片段)

[C] KMP算法实现 →→→→→进入此内容的聊天室

来自 , 2020-08-08, 写在 C, 查看 147 次.
URL http://www.code666.cn/view/d16509f6
  1. void get_nextval(char s[],int nextval[])//求模式串S的nextval函数值并存入到nextval[]中
  2. {
  3.    int i=0,j=-1;
  4.    nextval[0]=-1;
  5.    while(i<strlen(s))
  6.   {
  7.      if(j==-1||s[i]==s[j])
  8.      {
  9.       ++i;  ++j;
  10.      if(s[i]!=s[j])
  11.        nextval[i]=j;
  12.       else
  13.        nextval[i]=nextval[j];
  14.      }
  15.   else
  16.     j=nextval[j];
  17.   }
  18. }
  19.  
  20. int KMP(char s[],char t[],int nextval[])//利用模式串t的nextval函数求t的主串s
  21. {
  22.    int ls=strlen(s);
  23.    int lt=strlen(t);
  24.    int i=0,j=0,len=0;
  25.  
  26.    while(i<=ls&&j<=lt)
  27.    {
  28.      if(j==-1||s[i]==t[j])//继续比较后继字符
  29.       {  ++i;  ++j; }
  30.      else
  31.       j=nextval[j]; //  模式串向右移动
  32.      if(j==lt)//通过nextval[]求得的j如果和模式串的长度相等就说明模式串在主串中出现了；
  33.      {
  34.       len++;
  35.       j=nextval[j];
  36.      }
  37.    }
  38.    return len;
  39. }

回复 "KMP算法实现"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666