一江春水向东流

做一个有思想的人,期待与每一位热爱思考的人交流,您的关注是对我最大的支持。

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  44 随笔 :: 139 文章 :: 81 评论 :: 0 Trackbacks

KMP算法的关键是根据给定的模式串W[1,m],定义一个next函数。next函数包含了模式串本身局部匹配的信息。
   KMP算法的基本思想是:假设在模式匹配的进程中,执行T[i]和W[j]的匹配检查。若T[i]=W[j],则继续检查T[i+1]和W[j+1]是否匹配。若T[i]<>W[j],则分成两种情况:若j=1,则模式串右移一位,检查T[i+1]和W[1]是否匹配;若1<j<=m,则模式串右移j-next(j)位,检查T[i]和W[next(j)]是否匹配。重复此过程直到j=m或i=n结束。

/**************************************
 *
 *  KMP字符串匹配算法
 *
 *
 **************************************/
#include <stdio.h>
#include <string.h>
int next[10];
void getnext(char *p)
{
 int idx_p, len_p, k;
 
 idx_p = 0;
 len_p = strlen(p);
 k = -1;
 next[0] = -1;
 
 while(idx_p < len_p -1)
 {
  if ((k == -1) || *(p+idx_p) == *(p+k))
  {
   idx_p = idx_p + 1;
   k = k + 1;
   next[idx_p] = k;
  }
  else
  {
   k = next[k];
  }
 }
}
int kmp(char *s, char *p)
{
 int len_p, len_s, idx_p, idx_s;
 
 len_p = strlen(p);
 len_s = strlen(s);
 idx_p = idx_s = 0;
 
 while ((idx_p < len_p) && (idx_s < len_s))
 {
  /* 字符匹配或者要比较p中的第一个字符 */
  if ((idx_p == -1) || *(p+idx_p) == *(s+idx_s))
  {
   idx_p = idx_p + 1; idx_s = idx_s +1;
  }
  else
  {
   idx_p = next[idx_p];
  }
 }
 if (idx_p >= len_p)
 {
  return (idx_s - len_p);
 }
 else
 {
  return -1;
 }
}
int main()
{
 int pos, i;
 char s[50] = "abaaaabcabcacb";
 char p[10] = "aaaabca";
 
 getnext(p);
 if ((pos = kmp(s, p)) == -1)
 {
  fprintf(stderr, "String \"%s\" doesn't contain Pattern \"%s\"!\n", s, p);
 }
 else
 {
  printf("String \"%s\" contains Pattern \"%s\".\n The position of fisrt occur is %d\n", s, p, pos);
  printf("%s\n", s);
  for (i = 0; i < pos; i++)
   printf(" ");
  printf("%s\n", p);
 }
 return 0;
}

posted on 2007-04-29 15:52 allic 阅读(1270) 评论(0)  编辑  收藏 所属分类: 算法及数据结构

只有注册用户登录后才能发表评论。


网站导航: