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             else180             {181                 printf(" ");182             }183         }184         printf("\nEnd Position:%d",end);185     }186     else187     {188         printf("结果出错了！");189     }190     Delete(&array,b);191     return 1;192 }