kmp 算法 --转

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#define MAX 256

void getNext(const char * t,int * Next)//get the Next array
{
 int k=-1;
 int j=0;
 int size=strlen(t);
 Next[0]=-1;
 while(j<size)
 {
  if(k==-1||t[j]==t[k])//if k==-1 there are two conditions
   //one is this is the first time entering the loop
  {   //if t[j]==t[k] get the next[j+1] directly
   k++;//the other is the end of the iteration cos k==-1;
   j++;
   Next[j]=k;//whatever Next[j]=k 
  }
  else
   k=Next[k];
 }
}

int kmp(const char * Dest,const char *subStr)//find the starting position of the sub
{                                                 //in the Dest through KMP
 int destSize=strlen(Dest);
 int subSize=strlen(subStr);
 int i,j;
 int Next[MAX];
 i=j=0;
 assert((Dest!=NULL)&&(subStr!=NULL));
 getNext(subStr,Next);
 while(i<destSize&&j<subSize)
 {
  if(j==-1||Dest[i]==subStr[j])//if j==-1 the main string need match the next elements
  {                            //and the subString begin from the beginning
    i++;                     //if Dest[i]==subStr[j]  both string need shift to the
    j++;                     // next elements
  }
  else
    j=Next[j];                   //if match fail,glide back to Next[j]
 }
 if(j==subSize)return i-j;
 return -1;
}

 

int main()
{
 char Dest[]="ssdfdsskdjfkds";//to store the substring to be matched
 char sub[]="fffff";
 printf("the starting position is :%d\n",kmp(Dest,sub));//get the starting position
 getchar();
 getchar();
 return 0;
}

评论

1 楼 a06062125 2011-01-03  

只有代码没有讲解 这也算日志