Board logo

标题: [分享] 数据结构--串的应用，模式匹配算法（从简单算法到改进的KMP算法） [打印本页]
作者: 悠然南山    时间: 2012-2-4 22:51     标题: 数据结构--串的应用，模式匹配算法（从简单算法到改进的KMP算法）

这一篇写的模式匹配算法是以上一篇串的基本操作为基础的，这里面写了模式匹配的三种不同的算法，其实每个算法都是前一算法的改进，有简单匹配，头尾匹配，还有改进后KMP算法

这是文件fun.h:
  1. #ifndef FUN_H
  2. #define FUN_H
  3. #include "mystring.h"

  5. int Index(String *sub,String *s,int pos); //匹配的简单算法：返回子串sub在主串s中的位置，失败则返回0
  6. int Index_HeadToTail(String *sub,String *s,int pos);//匹配的改进算法：头尾同时进行比较
  7. void get_next(String *,int []);    //KMP算法中的next函数算法
  8. int kmp(String *s,String *T,int [],int pos); //KMP的改进算法

  10. int Index(String *sub,String *s,int pos)
  11. {
  12. int i,j;
  13. if(pos<0||pos>s->length)  exit(OVERFLOW);
  14. i=pos-1;
  15. j=0;
  16. while(i<s->length && j<sub->length)
  17. {
  18.   if(s->ch[i]==sub->ch[j])
  19.   {
  20.    ++i;++j;
  21.   }
  22.   else
  23.   {
  24.    i=i-j+2;
  25.    j=0;
  26.   }
  27.     }
  28. if(j==sub->length)  
  29. {
  30.   printf("Success!");
  31.   TURNLINE;
  32.   return i-sub->length;//匹配成功，并且此时i,j的位置都在'\0'上，则返回在主串中匹配的第一个位置
  33. }
  34. else
  35. {
  36.   printf("Failed!");
  37.   TURNLINE;
  38.   return 0;
  39. }
  40. }
  41. int Index_HeadToTail(String *sub,String *s,int pos)
  42. {
  43. int i,j=1,k=1;
  44. i=pos-1;
  45. while(i<s->length)
  46. {
  47.   if(s->ch[i]!=sub->ch[0]) ++i;  //如果头字符匹配不成功则继续匹配下一个
  48.   else if (s->ch[i+sub->length-1]!=sub->ch[sub->length-1])  ++i; //如果头字符匹配成功，但尾字符匹配不成功，继续匹配下一个
  49.   else
  50.   {  
  51.      while(j<sub->length && s->ch[i+k]==sub->ch[j])
  52.      {
  53.       ++k;++j;
  54.      }
  55.      if(j==sub->length)  
  56.      {
  57.       printf("Success!");
  58.       TURNLINE;
  59.       return i;
  60.      }
  61.      else
  62.      {
  63.       printf("Failed");
  64.       TURNLINE;
  65.       return 0;
  66.      }
  67.   }
  68. }
  69. return 0;
  70. }

  72. void get_next(String *s,int next[])
  73. {
  74. int i,j;
  75.     next[0]=-1;
  76. i=0;
  77. j=-1;
  78. while(i<s->length)
  79. {
  80.   if(j==-1||s->ch[i]==s->ch[j])
  81.   {
  82.    ++i;
  83.    ++j;
  84.    if(s->ch[i]!=s->ch[j])  next[i]=j;
  85.    else next[i]=next[j];
  86.   }
  87.   else j=next[j];
  88. }
  89. }
  90. int kmp(String *s,String *T,int next[],int pos)
  91. {
  92. int i,j;
  93.    
  94. if(pos<1||pos>s->length)
  95.           exit(OVERFLOW);
  96. i=pos-1;
  97. j=0;
  98. while(i<s->length && j<T->length)
  99. {
  100.   if(s->ch[i]==T->ch[j] || j==-1)
  101.   {
  102.    ++i;
  103.    ++j;
  104.   }
  105.   else j=next[j];
  106. }
  107. if(j==T->length)
  108. {
  109.   printf("Success!");
  110.   TURNLINE;
  111.   return   i-T->length;
  112. }
  113. else
  114. {
  115.   printf("Failed!");
  116.   TURNLINE;
  117.   return 0;
  118. }
  119. }

  121. #endif
复制代码
这是mian函数：
  1. #include "mystring.h"
  2. #include "fun.h"
  3. int main()
  4. {
  5. String str1,str2,str3;
  6. int index,next[10];
  7. int i;
  8. char *chars="aaaababaabcacaabc\0";
  9. char *chars1="ababa\0";

  11. strAssign(&str1,chars);
  12. /*strCopy(&str1,&str2);*/

  14. strAssign(&str2,chars1);
  15. get_next(&str2,next);
  16. strPrint(&str1);
  17. strPrint(&str2);
  18. for(i=0;i<5;++i)
  19. printf("%3d",next[i]);TURNLINE;

  21. index=kmp(&str1,&str2,next,1);
  22. printf("%d\n",index);
  23. return 0;
  24. }
复制代码




欢迎光临 IT家园 (http://bbs.it998.com/) Powered by Discuz! 7.2