KMP算法

Code Begin

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 该函数求最长公共前后缀 */
void prefix_table(char ptrn[], int prefix[], int n)
{
   int len=0;
   int i=1;
   prefix[0]=0;
   while(i<n){
      printf("i = %d, len = %d\n",i,len);
      if(ptrn[i]==ptrn[len]){
         len++;
         prefix[i]=len;
         i++;
      }else{
         if(len>0){
            len=prefix[len-1];
         }else{
            prefix[i]=len;/* 这里的len其实就是0,所以也可以直接写0 */
            i++;
         }
      }
   }
}
/* 经过move之后,则在prefix[i]表示的是i之前的字符串最长公共前后缀的长度 */
void move_prefix_table(int prefix[],int n)
{
   int i;
   for(i=n-1;i>0;i--){
      prefix[i]=prefix[i-1];
   }
   prefix[0]=-1;
}

void kmp_search(char text[], char ptrn[])
{
   int n=strlen(ptrn);
   int m=strlen(text);
   int i=0;
   int j=0;
   int* prefix=(int *)malloc(sizeof(int)*n);
   prefix_table(ptrn,prefix,n);
   move_prefix_table(prefix,n);

   /* text[i] len(text)=m */
   /* ptrn[j] len(ptrn)=n */
   while(i<m){
      if(j==n-1 && text[i]==ptrn[j]){
         printf("Found pattern at %d\n", i-j);
         j=prefix[j];/* 继续寻找下一个相同的匹配, 如果只需找一个那么可以break */
      }
      if(text[i]==ptrn[j]){
         i++;j++;
      }else{
         /* 从相同的前缀后开始比较,因为后缀和前缀相同,后缀相同了,前缀必然相同 */
         j=prefix[j];
         if(j==-1){
            i++;j++;
         }
      }
   }
}

int main(int argc, char* argv[])
{
   /* 对于本例prefix[] 为-1 0 0 1 2 0 1 2 3 */
   char ptrn[]="ABABCABAA";
   char text[]="ABABABCABAABABABAB";

   kmp_search(text,ptrn);
#if 0
   int prefix[9];
   int n=9;
   int i;
   prefix_table(ptrn, prefix,9);
   move_prefix_table(prefix,n);
   for(i=0;i<n;i++)
      printf("%d ",prefix[i]);
   printf("\n");
#endif
   return 0;
}
/*
Found pattern at 2
*/

Code end