KMP_Algorithm.rar

#include "stdio.h" #include "string.h" #define STOP "quit" #define GINGALS "/n*******************************/n" // int KMPIndex(const char *T,const char *P,int pos); void getNext(const char *P,int next[]); int KMPIndexHelp(const char *T,const char *P,int pos,int next[]); int main(void) { char pattern_str[1001]; char target_str[1001]; int position; printf("\nenter the target str :(exit with quit)\n"); gets(target_str); //putchar('\n'); //puts(pattern_str); printf("\nenter the pattern str:(exit with quit)\n"); gets(pattern_str); //putchar('\n'); //puts(target_str); while ((strcmp(pattern_str,STOP))&&(strcmp(target_str,STOP))) { printf("\nthe target str is: %s\n ",target_str); printf("\nthe pattern str is: %s\n ",pattern_str); position=KMPIndex(target_str,pattern_str,0); printf("\nthe position of pattern str in the target str is: %d\n",position); printf("\nenter the target str :(exit with quit)\n"); gets(target_str); printf("\nenter the pattern str:(exit with quit)\n"); gets(pattern_str); } return 1; } int KMPIndex(const char *T,const char *P,int pos) { int *next=new int[strlen(P)]; getNext(P,next); int result=KMPIndexHelp(T,P,pos,next); printf("\n%s\n",GINGALS); delete []next; return result; } void getNext(const char *P,int next[]) { next[0]=-1; int j=0,k=-1; while(j<(strlen(P)-1)) { if(k==-1) { next[j+1]=0; j=1;k=0; } else if(P[k]==P[j]) { next[j+1]=k+1; j++;k++; } else { k=next[k]; } } for (int m=0;m<strlen(P);m++) { printf(" %d ",next[m]); } } int KMPIndexHelp(const char *T,const char *P,int pos,int next[]) { int i=pos,j=0; while ((i<strlen(T))&&(j<strlen(P))) { if(j==-1) { i++;j=0; } else if (P[j]==P[i]) { i++;j++; } else { j=next[j]; } } if(j<strlen(P)) return -1; else return i-j; }