kmp.c

ＢＦ和ＫＭＰ算法实例

/*kmp算法*/ 
int pmatch(char t[],char p[],int next[])
  {
  int i,j,n;
  i=0;
  j=0;
  while(i<strlen(p)&&j<strlen(t))
  if(i==-1||p[i]==t[j])
  { i++;j++;}
  else
  { display(t,p,j,i);

  i=next[i]; }
  if(i>=strlen(p))
  { display(t,p,j,i);return(j-strlen(p)+1);}
  else return -1;
  }

  makenext(char p[],int next[])
  {
  int i,k=-1;
  i=0;
  next[0]=-1;
  while(i<strlen(p)-1)
  {
   while(k>=0&&p[i]!=p[k])
   k=next[k];
   i++; k++;
   if(p[i]==p[k])
   next[i]=next[k];
   else next[i]=k;
   }
   }
   display(char s[],char t[],int i,int j)
   {
   int n;
   for(n=0;n<strlen(s);n++)
   printf(" %c",s[n]); printf("\n");
   for(n=0;n<i-j;n++) printf("  ");
   for(n=0;n<strlen(t);n++) printf(" %c",t[n]); printf("\n\n");
   }
   main()
   {
   char a[50],b[50];
   int next[50],i;
   printf("Enter string a:");
   scanf("%s",a);
   printf("Enter string b:");
   scanf("%s",b);
   makenext(b,next);
   i=pmatch(a,b,next);
   printf("The result is  %d\n",i);
   getch();
   }