ITPub博客

首页 > Linux操作系统 > Linux操作系统 > KMP算法详解

KMP算法详解

原创 Linux操作系统 作者:licup123 时间:2009-02-08 01:05:10 0 删除 编辑

        温习严蔚敏老师的数据结构模式匹配算法的一点理解,希望对有些朋友有点用途。

        算法的描述:假设主串为‘s1s2……sn’,模式串是'p1p2……pn'关键是匹配过程中失配时模式串向右移动几位(假设为K)则可以得到如下两个式子:

式子一  ‘P1P2……Pk-1’=‘Si-k+1Si-k+2……Si-1’

式子二‘Pj-k+1Pj-k+2……Pj-1’=‘Si-k+1Si-k+2……Si-1’

上面的式子通俗一点的表达就是,k'必须要使得p[1..k]中的头k'个字母和末k'个字母完全相等(这样k变成了k'后才能继续保持i和j的性质)。

完整代码如下:

#include
#include
#include
using namespace std;
typedef struct
{
 char *chars;
 int length;
}SString;
bool StrAssign(SString &T,char *ch)
{
 char *c;
 if(T.chars==NULL)
  free(T.chars);
 c=ch;
 int i=0;
 while(*c)
 {++i;++c;}
 if(!i){T.chars=NULL;T.length=0;}
 else
 {
  if(!(T.chars=(char*)malloc((i+1)*sizeof(char))))
   return 0;
  T.length=i;
  for(i=1;i   T.chars[i]=ch[i-1];
 }
  return 1;
}
void get_next(SString T,int next[])
{
 int i=1;
 next[1]=0;
 int j=0;
 while(i {
  if(j==0||T.chars[i]==T.chars[j])
  {
   ++i;++j;
      next[i]=j;next[i]=j;
  }
  else j=next[j];
 }
}
int Index_KMP(SString S,SString T,int pos,int next[])
{
 int i=pos;
 int j=1;
 while(i<=S.length&&j<=T.length)
 {
  if(j==0||S.chars[i]==T.chars[j]){++i;++j;}
  else j=next[j];
 }
 if(j>T.length) return i-T.length;
 else return 0;
}
void main(void)
{
 int i=0;
 int next[9]={0};
    char str[]="abaabcac";
 char str1[]="acabaabaabcacaabc";
 SString t,t1;
 t.chars=NULL;t1.length=0;
 t1.chars=NULL;t1.length=0;
    StrAssign(t,str);
    StrAssign(t1,str1);
 get_next(t,next);
    int index=Index_KMP(t1,t,1,next);
}

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10697500/viewspace-545540/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2008-06-22

  • 博文量
    51
  • 访问量
    117486