模式匹配

模式匹配算法有两种，一种是朴素模式匹配，一种是无回溯模式匹配

朴素模式匹配：

定义结构体的头文件:

 1 #ifndef mach_A
 2 #define mach_A 1
 3 struct SeqString {
 4     int n;
 5     char *c;
 6 };
 7 #endif
 8 
 9 typedef struct SeqString * PSeqString;
10 
11 
12 PSeqString createEmptyString(int size)
13 {
14     PSeqString pss = NULL;
15     pss = (PSeqString)malloc(sizeof(struct SeqString));
16     if(NULL != pss)
17     {
18             pss->n = size;    
19             pss->c = NULL;
20     }
21     return pss;
22 }

测试：

 1 #include "stdio.h"
 2 #include "stdlib.h"
 3 #include "seqstring.h"
 4 
 5 /************************************************************************/
 6 /* 朴素模式匹配算法
 7    求p所指串在t所指串第一次出现时，p所指串的第一个元素在t所指串中的序号                                                                     */
 8 /************************************************************************/
 9 int index(PSeqString t, PSeqString p)
10 {
11     int i, j; //i为p串当前字符的下标，j为t串中当前字符的下标
12     i = 0; j = 0;
13     while(i < p->n && j < t->n)
14     {
15         if(p->c[i] == t->c[j]) //继续匹配下一个字符
16         {
17             i++;
18             j++;        
19         }
20         else  //回溯，重新进行下一次匹配
21         {
22             j = j - i + 1;
23             i = 0;
24         }
25     }
26     if(i >= p->n) //匹配成功
27         return j - p->n + 1; 
28     else return -1; //匹配失败
29 }
30 
31 int main()
32 {    
33     
34     PSeqString p = NULL;
35     PSeqString t = NULL;
36     char *a,*b;
37     int i;
38 
39     i = 0;
40     a = "abcdaefga";
41     b = "bcda";
42     p = createEmptyString(4);
43     t = createEmptyString(9);
44 
45     p->c = b;
46     t->c = a;
47     i = index(t, p);
48     printf("index is %d\n", i);
49 
50 
51     return 0;
52 }

第9~29行是朴素模式匹配算法的核心。

无回溯模式匹配：

结构体的定义：

 1 #ifndef mach_A
 2 #define mach_A 1
 3 #define MaxNum 100
 4 struct SeqString {
 5     int n;
 6     char c[MaxNum];
 7 };
 8 #endif
 9 
10 typedef struct SeqString * PSeqString;
11 
12 
13 PSeqString creatnullstring()
14 {
15     PSeqString str;
16     str=(PSeqString)malloc(sizeof(struct SeqString));
17     if(str==NULL)
18         printf("OUT OF SPACE!");
19     else
20         str->n=0;
21     return str;
22 }

测试：

 1 #include "stdio.h"
 2 #include "stdlib.h"
 3 #include "string.h"
 4 #include "seqstring.h"
 5 
 6 /*生成NEXT数组*/
 7 void makenext(PSeqString p,int *next)
 8 {
 9     int i=0,k=-1;
10     next[0]=-1;
11     while(i<p->n-1)
12     {
13         while(k>=0&&p->c[i]!=p->c[k])
14             k=next[k];
15         i++;
16         k++;
17         if(p->c[i]==p->c[k])
18             next[i]=next[k];
19         else
20             next[i]=k;
21     }
22 }
23 
24 
25 /*无回溯模式匹配算法*/
26 int index(PSeqString t,PSeqString p,int *next)
27 {
28     int i=0,j=0;
29     while(i<p->n&&j<t->n)
30         if(i==-1||p->c[i]==t->c[j])
31         {i++;
32         j++;
33         }
34         else
35             i=next[i];
36         if(i>=p->n)
37             return(j-p->n+1);
38         else
39             return -1;
40 }
41 
42 
43 int main(void)
44 {
45     int *next,result;
46     PSeqString str_t,str_p;
47     str_t=creatnullstring();
48     str_p=creatnullstring();
49     printf("\nPlease input T string:");
50     scanf("%s",str_t->c);
51     str_t->n=strlen(str_t->c);
52     printf("\nPlease input P string:");
53     scanf("%s",str_p->c);
54     str_p->n=strlen(str_p->c);
55     next=(int *)calloc(strlen(str_p->c),sizeof(int));
56     makenext(str_p,next);
57     result=index(str_t,str_p,next);
58     if(result)
59         printf("SUCCESS!!   %d\n",result);
60     else
61         printf("FALUSE");
62     free(str_p);
63     free(str_t);
64     return(0);
65 }

无回溯模式匹配最关键是求出next数组，第7到22行为求next数组的算法

一颗平常心，踏踏实实，平静对待一切