字符串匹配算法 之 基于DFA(确定性有限自动机)

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 #define ALPHABETLENGTH 53
  5 #define GETMIN(x,y) ((x)<=(y)?(x):(y))
  6  
  7 //判定pattern的前k个字符是不是（pattern的前q个字符加上字符a组成的）字符串的后缀
  8 int IsSuffix(char *pattern,int k,int q,char a);
  9 //创建自动机（二维数组），并且根据给定的pattern完成自动机的初始化
 10 void Create(int*** array,char *pattern);
 11 //根据创建的自动机进行模式匹配，并返回模式在给定文本中第一次出现的结束位置
 12 int DFAMatcher(char* T,int** array,char *pattern);
 13 //在程序结束时，将创建的自动机（二维数组）进行销毁
 14 void Delete(int*** array,char *pattern);
 15 //一个小函数，用来查找给定的字符a在预先设定的字母表中的位置
 16 int SearchChar(char a);
 17 //预先设定的字母表，包括26个大小写的字母以及一个空格，共53个字符
 18 char alphabet[ALPHABETLENGTH]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ";
 19  
 20 /*
 21 *通过函数来进行二维数组的分配，需要用到三重指针，传进去的是一个指针数组的地址，
 22 *直接传指针数组的话会造成悬垂指针，数组的构建需要根据pattern来构建
 23 *二维数组实际上就相当于自动机（DFA）了
 24 */
 25 void Create(int*** array,char *pattern)
 26 {
 27     //临时变量
 28     int i,j,k;
 29     //pattern的长度
 30     int patternlength=strlen(pattern);
 31     //二位数组的行数等于pattern中字符数加1
 32     int x=strlen(pattern)+1;
 33     //二维数组的列数等于字母表中所有的字符个数，这里我采用的是26个小写字母加上26个大写字母
 34     int y=ALPHABETLENGTH;
 35     //开始分配二维数组的空间，如果分配失败的话则要撤销已分配的单元。这里分两种情况，
 36     //一种是一开始就没有空间可分配，另一种是分配了一部分以后空间不足。
 37     *array=(int**)malloc(sizeof(int)*x);
 38     if(NULL==array)
 39     {
 40         fprintf(stderr,"\nspace is not enough!\n");
 41         return;
 42     }
 43     for(i=0; i<x; i++)
 44     {
 45         if(((*array)[i]=(int*)malloc(sizeof(int)*y))==NULL)
 46         {
 47             while(--i>=0)
 48             {
 49                 free((*array)[i]);
 50             }
 51             free(*array);
 52             fprintf(stderr,"\nspace is not enough!\n");
 53             return;
 54         }
 55     }
 56     //下面开始初始化二维数组的自动机表了
 57     for(i=0; i<=patternlength; i++)
 58     {
 59         for(j=0; j<ALPHABETLENGTH; j++)
 60         {
 61             k=GETMIN(patternlength+1,i+2);
 62             do
 63             {
 64                 --k;
 65  
 66             }
 67             while(k>0 && !IsSuffix(pattern,k,i,alphabet[j]));
 68             (*array)[i][j]=k;
 69         }
 70     }
 71     for(i=0; i<patternlength+1; i++)
 72     {
 73         for(j=0; j<ALPHABETLENGTH; j++)
 74         {
 75             printf("%d ",(*array)[i][j]);
 76         }
 77         printf("\n");
 78     }
 79 }
 80  
 81 //为了实现Pk是Pqa的后缀，k和q是字符数组P的下标表示数组P的前k和前q个字符，a是一个字符表示连接在字符串Pq后面
 82 int IsSuffix(char *pattern,int k,int q,char a)
 83 {
 84     int cmp;
 85     char Q[q+1];
 86     Q[q]=a;
 87     strncpy(Q,pattern,q);
 88     cmp=strncmp(pattern,Q+q-(k-1),k);
 89     if(cmp==0)
 90     {
 91         return 1;
 92     }
 93     else
 94     {
 95         return 0;
 96     }
 97 }
 98  
 99 //查找字符变量a在字母表中的位置
100 int SearchChar(char a)
101 {
102     int i=0;
103     while(alphabet[i]!=a)
104     {
105         ++i;
106     }
107     if(i>(ALPHABETLENGTH-1))
108     {
109         i=-1;
110     }
111     return i;
112 }
113 //利用自动机进行匹配
114 int DFAMatcher(char* T,int** array,char *pattern)
115 {
116     int i;
117     int n=strlen(T);
118     int m=strlen(pattern);
119     int q=0;
120     int position=0;
121  
122     for(i=0; i<n; i++)
123     {
124         position=SearchChar(T[i]);
125         if(position<0)
126         {
127             fprintf(stderr,"字符[%c]不存在\n",T[i]);
128             return -1;
129         }
130         q=array[q][position];
131         if(q==m)
132         {
133             printf("find!\n");
134             break;
135         }
136     }
137     if(q!=m)
138     {
139         printf("unfind\n");
140         i=-1;
141     }
142     return i;//如果匹配成功返回pattern在字符串的结束位置，否则返回-1；
143 }
144 //程序结束进行销毁二维数组
145 void Delete(int*** array,char *pattern)
146 {
147     int i;
148     int m=strlen(pattern);
149     for(i=m; i>=0; i--)
150     {
151         free((*array)[i]);
152     }
153     free((*array));
154 }
155  
156 int main(void)
157 {
158     char a[100]="defabcababacaghijkl";
159     char b[10]="ababaca";
160     int **array;
161     int i;
162     printf("开始构建自动机：\n");
163     Create(&array,b);
164     printf("自动机构建完毕!\n");
165     int end=DFAMatcher(a,array,b);
166     int first=end-strlen(b)+1;
167     if(end>=0)
168     {
169         printf("输入字符串：%s\n",a);
170         printf("模式：%s\n",b);
171         printf("结果：\n");
172         printf("%s\n",a);
173         for(i=0; i<strlen(a); i++)
174         {
175             if(i==end || i==first)
176             {
177                 printf("|");
178             }
179             else
180             {
181                 printf(" ");
182             }
183         }
184         printf("\nEnd Position:%d",end);
185     }
186     else
187     {
188         printf("结果出错了！");
189     }
190     Delete(&array,b);
191     return 1;
192 }