[分享] 数据结构--串的应用，模式匹配算法（从简单算法到改进的KMP算法）

悠然南山

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

这是文件fun.h:

1. #ifndef FUN_H
   
2. #define FUN_H
   
3. #include "mystring.h"
   
4. 
   
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的改进算法
   
9. 
   
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. }
    
71. 
    
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. }
     
120. 
     
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";
   
10. 
    
11. strAssign(&str1,chars);
    
12. /*strCopy(&str1,&str2);*/
    
13. 
    
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;
    
20. 
    
21. index=kmp(&str1,&str2,next,1);
    
22. printf("%d\n",index);
    
23. return 0;
    
24. }

复制代码