ch4_string_match.c

本人讲授数据结构课程时的所写的示例程序

/*
串的模式匹配
author: kk.h
date: 2006.10
http://www.cocoon.org.cn
*/

#define MaxStrLen 200

/* 字符串赋值，把串source复制到target中 */
int StrAssign(char* target,char *source)
{
  int i=0;
  for(target[0]=source[0];source[i]!='\0';i++)
    target[i]=source[i];
  target[i]=source[i];
  return 1;
}

/* 返回子串t在主串s中第pos个字符之后的位置。若不存在，则返回0 */
/* 注意C语言的下标是从0开始，和书上不同 */
int Index(char* s,char* t,int pos)
{
  int i,j,ls,lt;
  i=pos-1,j=0;
  ls=strlen(s); lt=strlen(t);
  while(i<ls && j<lt) {
    if(s[i]==t[j]) {
      i++; j++;
    }
    else {
      i=i-j+1;
      j=0;
    }
  }

  if (j>=lt) return i-lt+1;
  else return 0;
}

/* 和以上函数功能相同，算法不同(KMP算法)，效率更高 */
int Index_KMP(char* s,char* t,int pos,int next[])
{
  int i,j,ls,lt;

  i=pos-1,j=-1;
  ls=strlen(s); lt=strlen(t);
  while(i<ls && j<lt) {
    if(j==-1 || s[i]==t[j]) {  /* 这一句和Index()不同 */
      i++; j++;
    }
    else {
      j=next[j]-1;  /* 这一句和Index()不同 */
    }
  }

  if (j>=lt) return i-lt+1;
  else return 0;

}

/* 用递推方法求next，注意C语言的下标是从0开始 */
get_next(char* s,int next[])
{
  int i,j;
  i=1; j=0;
  next[0]=0;

  while (i<strlen(s)) {
    if (j==0 || s[i-1]==s[j-1]) {
      i++; j++;
      next[i-1]=j;
    }
    else
      j=next[j-1];
  }
}

main()
{
  char s1[MaxStrLen],s2[MaxStrLen];
  int i,next[20];

  StrAssign(s1,"acabaabaabcacaabc");
  StrAssign(s2,"abaabc");

  get_next(s2,next);


  printf("\n%s",s1);
  printf("\n%s",s2);

  printf("\nnext=");
  for (i=0;i<strlen(s2);i++)
    printf("%d, ",next[i]);

  printf("\n%d",Index(s1,s2,1));
  printf("\n%d",Index_KMP(s1,s2,1,next));

  getch();
}