test2.c

是一个C语言的KMP代码

/*  KMP 算法体验 */


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

#define MAX (100)

main()
{
   char s[MAX],t[MAX],n[MAX];
   int lenS = 0 , lenT = 0;
   int i , j , p = 0;

   printf("enter the string first\n");
   scanf("%s",s+1);
   printf("enter the model second\n");
   scanf("%s",t+1);

   while(s[lenS+1]!='\0') lenS++;

   while(t[lenT+1]!='\0') lenT++;

   /*计算NEXT数组*/
   i = 1;
   j = 0;
   n[1] = 0;
   while(i<=lenT)
   {
      if(j==0||t[i]==t[j]) { n[i] = j ;i++; j++;}
      else j = n[j];
   }


   printf("this is the next []\n");
   for(i=0;i<lenT;i++)
   {
      printf("%d ,",n[i+1]);
   }

   printf("\n\n");

   /*匹配计算*/

   i=1;
   while(i<=lenS)
   {
      while(p>0&&t[p+1]!=s[i]) p = n[p];

      if(t[p+1]==s[i])
      {
         p = p+1;
      }

      if(p==lenT)
      {
        printf("Success!,start from %d",i-p+1);
        break;
      }

      i++;
   }

   if(p!=lenT) printf("\nit is not substring !");

   getch();

}