即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

KMP字符串查找算法

编程语言 qustDrJHJ 19℃ 0评论
#include 
#include 

void get_next(char *t,int *next)
{
 int i=0,j=-1;
 next[0]=-1;
 while(t[i]!='\0')
 {
  if(j==-1 || t[i]==t[j])
  {
   i++,j++;
   printf("%d %d\n",i,j);
   if(t[i]!=t[j])
    next[i]=j;
   else
    next[i]=next[j];
  }
  else
   j=next[j];
 }
}
int KMP(char *s,char *t,int *next)
{
 if(s==NULL || t==NULL)
  return -1;
 int i=0,j=0;
 int len=strlen(t);
 while(s[i]!='\0')
 {
  if(j==-1 || s[i]==t[j])
   i++,j++;
  else
   j=next[j];
  if(j==len)
   return i-len;
 }
 return -1;
}
int main(int argc,char **argv)
{
 char s[128]="asdfghjkabcabdkhi";
 char t[64]="abcabd";
 int next[64];
 int n=0;
 get_next(t,next);
 for(n=0;n<6;n++)
  printf(" %d",next[n]);
 printf("s:%s\n",s);
 printf("t:%s\n",t);
 printf("%d\n",KMP(s,t,next));
 return 0;
}


转载请注明:CodingBlog » KMP字符串查找算法

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情