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

原文：http://www.91linux.com/html/article/program/cpp/20081017/13581.html

理论不再赘述，请参考算法导论一书，第32章32.3节利用有限自动机进行字符串匹配，本文主要给出了C语言的具体实现，关键地方都加上了注释。


  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," space is not enough! ");
  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," space is not enough! ");
  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(" ");
  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]不存在 ",T[i]);
  128.             return -1;
  129.         }
  130.         q=array[q][position];
  131.         if(q==m)
  132.         {
  133.             printf("find! ");
  134.             break;
  135.         }
  136.     }
  137.     if(q!=m)
  138.     {
  139.         printf("unfind ");
  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("开始构建自动机： ");
  163.     Create(&array,b);
  164.     printf("自动机构建完毕! ");
  165.     int end=DFAMatcher(a,array,b);
  166.     int first=end-strlen(b)+1;
  167.     if(end>=0)
  168.     {
  169.         printf("输入字符串：%s ",a);
  170.         printf("模式：%s ",b);
  171.         printf("结果： ");
  172.         printf("%s ",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(" End Position:%d",end);
  185.     }
  186.     else
  187.     {
  188.         printf("结果出错了！");
  189.     }
  190.     Delete(&array,b);
  191.     return 1;
  192. }

阅读(969) | 评论(0) | 转发(1) |
0

上一篇：linux c/c++ GDB教程详解

下一篇：有效运用auto_ptr

相关热门文章
给主人留下些什么吧！~~
评论热议
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/black/p/5171702.html