确定有限自动机定义：

自动机在字符串匹配中的应用

1 #include
     
        2 #include
      
         3 #include
       
          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
        
         =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
         
          0 && !IsSuffix(pattern,k,i,alphabet[j])); 68             (*array)[i][j]=k; 69         } 70     } 71     for(i=0; 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
           
            =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
           
          
         
        
       
      
     

代码参考：