KMP算法原理与实现（模式匹配）

    模式匹配的一种改进算法----KMP算法

这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特算法（简称为KMP算法）。该算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的‘部分匹配’的结果将模式向右‘滑动’尽可能远的一段距离后，继续进行比较。

一般情况下，假设主串为s0s1…sn-1，模式串为p0p1…pm-1，从上例的分析可知，为了实现改进算法，需要解决下述问题：当匹配过程中产生“失配”（即si≠pj）时，模式串“向右滑动”可行的距离有多远，换句话说，当主串中字符Si与模式中字符Pj “失配”（即比较不等）时，主串中字符Si（i指针不回溯）应与模式中哪个字符再比较？
   假设此时主串中字符Si应与模式中字符Pk（k＜j）继续比较，则模式中字符Pk前面k个字符的子串必须满足下列关系式（f-1），且不存在k'＞k满足下列关系式
p0p1…pk-1= si-ksi-k+1…si-1   （f-1）
当主串中字符Si与模式中字符Pj “失配”时，已经得到的“部分”匹配结果是：
pj-kpj-k+1…pj-1= si-ksi-k+1…si-1 （f-2）
由（f-1）和（f-2）推得下列等式
p0p1…pk-1 = pj-kpj-k+1…pj-1    (f-3)
我们称"p0p1…pk-1"为"p0p1p2…pj-2pj-1"的前缀子串，"pj-kpj-k+1…pj-1"为"p0p1p2…pj-2pj-1"的后缀子串。
若模式串中存在真子串"p0p1…pk-1= pj-kpj-k+1…pj-1"，且满足0

若令next[j]=k,则next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。由此可引出模式串的next函数的定义：

1.next[j]=-1 当j=0时

2.next[j]=Max{k|0

                      此集合不为空时

3.next[j]=1 其他情况

其中p0p1…pk-1为p0p1p2…pj-2pj-1的前缀子串，pj-kpj-k+1…pj-1为p0p1p2…pj-2pj-1的后缀子串。

KMP算法源代码如下：

#include

#include

#define MAXSIZE 100
void get_nextval(unsigned char pat[],int nextval[])
{
 int length = strlen(pat);
 int i=1;
 int j=0;
 nextval[1]=0;
 while(i {
  if(j==0||pat[i-1]==pat[j-1])
  {
   ++i;
   ++j;
   if(pat[i-1]!=pat[j-1]) nextval[i]=j;
   else nextval[i]=nextval[j];
  }
  else j=nextval[j];
 }
}
int Index_KMP(unsigned char text[], unsigned char pat[],int nextval[])
{
 int i=1;
 int j=1;
 int t_len = strlen(text);
 int p_len = strlen(pat);
 while (i<=t_len&&j<=p_len)
 {
  if(j==0||text[i-1]==pat[j-1]){++i;++j;}
  else j=nextval[j];
 }
 if (j>p_len) return i-1-p_len;
 else return -1;
}

int main()
{
    unsigned char text[MAXSIZE];
 unsigned char pat[MAXSIZE];
 int nextval[MAXSIZE];
 int answer, i;

 printf("\nBoyer-Moore String Searching Program");
 printf("\n====================================");
 printf("\n\nText String --> ");
 gets(text);
 printf( "\nPattern String --> ");
 gets(pat);
 get_nextval(pat,nextval);
 if((answer=Index_KMP(text, pat,nextval))>=0)
 {
  printf("\n");
  printf("%s\n", text);
  for (i = 0; i < answer; i++)
   printf(" ");
  printf("%s", pat);
  printf("\n\nPattern Found at location %d\n", answer);
 }
 else
  printf("\nPattern NOT FOUND.\n");

    return 0;
}