Chinaunix首页 | 论坛 | 博客
  • 博客访问: 557370
  • 博文数量: 104
  • 博客积分: 4131
  • 博客等级: 上校
  • 技术积分: 1137
  • 用 户 组: 普通用户
  • 注册时间: 2009-07-31 15:05
文章分类

全部博文(104)

文章存档

2011年(13)

2010年(23)

2009年(68)

我的朋友

分类: C/C++

2009-09-14 22:24:29

    模式匹配的一种改进算法----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;
}
 
阅读(961) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~