精华内容
下载资源
问答
  • 字符串模式匹配算法

    千次阅读 2017-04-05 15:19:03
    字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽     本文内容框架: §1 Boyer-Moore算法 §2 Horspool算法 §3 Sunday算法 §4 KMP算算法 §5 KR算法 §6 AC...

    字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽

     

     

    本文内容框架:

    §1 Boyer-Moore算法

    §2 Horspool算法

    §3 Sunday算法

    §4 KMP算算法

    §5 KR算法

    §6 AC自动机

    §7 小结

     

     §1 Boyer-Moore(BM)算法

     

    Boyer-Moore算法原理

     

    Boyer-Moore算法是一种基于后缀匹配的模式串匹配算法,后缀匹配就是模式串从右到左开始比较,但模式串的移动还是从左到右的。字符串匹配的关键就是模式串的如何移动才是最高效的,Boyer-Moore为了做到这点定义了两个规则:坏字符规则和好后缀规则,下面图解给出定义:

     

     

    下面分别针对利用坏字符规则和好后缀规则移动模式串进行介绍:

     

    坏字符规则

    1.如果坏字符没有出现在模式字符中,则直接将模式串移动到坏字符的下一个字符:

     



     (坏字符c,没有出现模式串P中,直接将P移动c的下一个位置)

    2.如果坏字符出现在模式串中,则将模式串最靠近好后缀的坏字符(当然这个实现就有点繁琐)与母串的坏字符对齐:


            (注:如果模式串P是babababab,则是将第二个b与母串的b对齐)

     

    好后缀规则

     

    好后缀规则分三种情况

    1.模式串中有子串匹配上好后缀,此时移动模式串,让该子串和好后缀对齐即可,如果超过一个子串匹配上好后缀,则选择最靠靠近好后缀的子串对齐。



     2.模式串中没有子串匹配上后后缀,此时需要寻找模式串的一个最长前缀,并让该前缀等于好后缀的后缀,寻找到该前缀后,让该前缀和好后缀对齐即可。


    其实,1和2都可以看成模式串还含有好后缀串(好后缀子串也是好后缀)。

    3.模式串中没有子串匹配上后后缀,并且在模式串中找不到最长前缀,让该前缀等于好后缀的后缀。此时,直接移动模式到好后缀的下一个字符。

     

     

    Boyer-Moore算法步骤

     

    1.对模式子串进行预处理

     

    Boyer-Moore算法实现必须对模式串进行预处理,得到坏字符规则和好后缀规则移动的映射表,下面代码中MakeSkip是建立坏字符规则移动的映射表,MakeShift是建立好后缀规则的移动映射表。

    MakeSkip是构造数组skip[],skip[k]表示字符k距离模式串末尾的距离。

    MakeShfit是构造数组shfit[],shfit[k]表示模式串的以k为边界的后缀子串的最靠近的模式子串(或最前缀子串)到模式子串末尾的距离,例如:abcab,shfit[3]=3和shfit[2]=3(即都是第一个b到末尾的距离),k=2时,后缀子串为cab,这时只有最长前缀ab,shfit[2]=3。

    2.从b_idx开始查找,得到坏字符和好后缀,得到最大移动距离,移动b_idx,直至b_idx到达母串的末尾。

     

     

    Boyer-Moore算法实现

     

    C代码   收藏代码
    1. /* 
    2.     函数:int* MakeSkip(char *, int) 
    3.     目的:根据坏字符规则做预处理,建立一张坏字符表 
    4.     参数: 
    5.         ptrn => 模式串P 
    6.         PLen => 模式串P长度 
    7.     返回: 
    8.         int* - 坏字符表 
    9. */  
    10. int* MakeSkip(char *ptrn, int pLen)  
    11. {     
    12.     int i;  
    13.     //为建立坏字符表,申请256个int的空间  
    14.     /*PS:之所以要申请256个,是因为一个字符是8位, 
    15.       所以字符可能有2的8次方即256种不同情况*/  
    16.     int *skip = (int*)malloc(256*sizeof(int));  
    17.   
    18.     if(skip == NULL)  
    19.     {  
    20.         fprintf(stderr, "malloc failed!");  
    21.         return 0;  
    22.     }     
    23.   
    24.     //初始化坏字符表,256个单元全部初始化为pLen,没有在模式串出现的字符距离为pLen。  
    25.     for(i = 0; i < 256; i++)  
    26.     {  
    27.         *(skip+i) = pLen;  
    28.     }  
    29.   
    30.     //给表中需要赋值的单元赋值,不在模式串中出现的字符就不用再赋值了  
    31.     while(pLen != 0)  
    32.     {  
    33.         *(skip+(unsigned char)*ptrn++) = pLen--;  
    34.     }  
    35.   
    36.     return skip;  
    37. }  
    38.   
    39.   
    40. /* 
    41.     函数:int* MakeShift(char *, int) 
    42.     目的:根据好后缀规则做预处理,建立一张好后缀表 
    43.     参数: 
    44.         ptrn => 模式串P 
    45.         PLen => 模式串P长度 
    46.     返回: 
    47.         int* - 好后缀表 
    48. */  
    49. int* MakeShift(char* ptrn,int pLen)  
    50. {  
    51.     //为好后缀表申请pLen个int的空间  
    52.     int *shift = (int*)malloc(pLen*sizeof(int));  
    53.     int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标  
    54.     char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标  
    55.     char c;  
    56.   
    57.     if(shift == NULL)  
    58.     {  
    59.         fprintf(stderr,"malloc failed!");  
    60.         return 0;  
    61.     }  
    62.   
    63.     c = *(ptrn + pLen - 1);//保存模式串中最后一个字符,因为要反复用到它  
    64.   
    65.     *sptr = 1;//以最后一个字符为边界时,确定移动1的距离  
    66.   
    67.     pptr--;//边界移动到倒数第二个字符(这句是我自己加上去的,因为我总觉得不加上去会有BUG,大家试试“abcdd”的情况,即末尾两位重复的情况)  
    68.   
    69.     while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作  
    70.     {  
    71.         char *p1 = ptrn + pLen - 2, *p2,*p3;  
    72.           
    73.         //该do...while循环完成以当前pptr所指的字符为边界时,要移动的距离  
    74.         do{  
    75.             while(p1 >= ptrn && *p1-- != c);//该空循环,寻找与最后一个字符c匹配的字符所指向的位置  
    76.               
    77.             p2 = ptrn + pLen - 2;  
    78.             p3 = p1;  
    79.               
    80.             while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//该空循环,判断在边界内字符匹配到了什么位置  
    81.   
    82.         }while(p3 >= ptrn && p2 >= pptr);  
    83.   
    84.         *sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中,以pptr所在字符为边界时,要移动的位置  
    85.         /* 
    86.           PS:在这里我要声明一句,*sptr = (shift + pLen - sptr) + p2 - p3; 
    87.              大家看被我用括号括起来的部分,如果只需要计算字符串移动的距离,那么括号中的那部分是不需要的。 
    88.              因为在字符串自左向右做匹配的时候,指标是一直向左移的,这里*sptr保存的内容,实际是指标要移动 
    89.              距离,而不是字符串移动的距离。我想SNORT是出于性能上的考虑,才这么做的。           
    90.         */  
    91.   
    92.         pptr--;//边界继续向前移动  
    93.     }  
    94.   
    95.     return shift;  
    96. }  
    97.   
    98.   
    99. /* 
    100.     函数:int* BMSearch(char *, int , char *, int, int *, int *) 
    101.     目的:判断文本串T中是否包含模式串P 
    102.     参数: 
    103.         buf => 文本串T 
    104.         blen => 文本串T长度 
    105.         ptrn => 模式串P 
    106.         PLen => 模式串P长度 
    107.         skip => 坏字符表 
    108.         shift => 好后缀表 
    109.     返回: 
    110.         int - 1表示成功(文本串包含模式串),0表示失败(文本串不包含模式串)。 
    111. */  
    112. int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)  
    113. {  
    114.     int b_idx = plen;    
    115.     if (plen == 0)  
    116.         return 1;  
    117.     while (b_idx <= blen)//计算字符串是否匹配到了尽头  
    118.     {  
    119.         int p_idx = plen, skip_stride, shift_stride;  
    120.         while (buf[--b_idx] == ptrn[--p_idx])//开始匹配  
    121.         {  
    122.             if (b_idx < 0)  
    123.                 return 0;  
    124.             if (p_idx == 0)  
    125.             {       
    126.                 return 1;  
    127.             }  
    128.         }  
    129.         skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳跃的距离  
    130.         shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离  
    131.         b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者  
    132.     }  
    133.     return 0;  
    134. }  

     ╝②

    算法的时间复杂度最差(匹配不上)是O(n×m),最好是O(n),其中n为母串的长度,m为模式串的长度。BM算法时间复杂度最好是O(n/(m+1))

     

    §2 Horspool算法

    horspool算法将主串中匹配窗口的最后一个字符跟模式串中的最后一个字符比较。如果相等,继续从后向前对主串和模式串进行比较,直到完全相等或者在某个字符处不匹配为止(如下图中的α与σ失配) 。如果不匹配,则根据主串匹配窗口中的最后一个字符β在模式串中的下一个出现位置将窗口向右移动。

    Horspool算法相对于Boyer-Moore算法改进了坏字符规则,Boyer-Moore算法只是将模式串P中从当前未匹配位置向右第一个坏字符与母串的坏字符(未匹配的字符)对齐进行再次匹配,Horspool算法是以当前匹配窗口中母串的最末尾的一个字符和模式串最靠近它的字符对齐,下图中β是当前匹配窗口的母串最后一个字符,将其与模式串左边最靠近的β对齐移动。


    Horspool算法预处理

     

    为了实现模式串的移动,必须先记录每一个字符串在模式串中距离最右边的距离:


    Horspool算法实现

    C代码   收藏代码
    1. /* 
    2.   * implementation of Horspool 
    3.   * Author:Horspool 
    4.   * Coder: Cobbliu 
    5.   */  
    6.  #define WORD 26  
    7.  int horspool(char *T, int lenT, char *P, int lenP)  
    8.  {  
    9.      int d[WORD];  
    10.      int i, pos, j;  
    11.    
    12.      for(i = 0; i != WORD; i++)  
    13.          d[i] = lenP;  
    14.      for(i = 0; i != (lenP-1); i++)  
    15.          d[P[i]-'A'] = lenP-i-1;  
    16.    
    17.      pos = 0;  
    18.      while(pos < (lenT-lenP)){  
    19.          j = lenP-1;  
    20.          while(j >= 0 && T[pos+j]==P[j])  //matching  
    21.              j--;  
    22.          if(j == -1)  
    23.              return pos;  
    24.          else //not matched  
    25.              pos += d[T[pos+lenP-1]-'A'];  
    26.      }  
    27.    
    28.      return -1;  
    29.  }  

     

    Horspool算法时间复杂度

     

    假设主串的长度为n,模式串的长度为m,那么Horspool算法最坏情况下的时间复杂度是O(mn),但平均情况下它的时间复杂度是O(n)。

    ╝④

    §3 Sunday算法

    Sunday算法思想跟BM算法很相似,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过,即移动步长= 匹配串长度+1;否则,同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。

    Sunday算法实现(不废话直接上代码)

     

    C代码   收藏代码
    1. #include <iostream>  
    2. #include <cstring>  
    3. using namespace std;  
    4.   
    5. int sunday(const char* src, const char* des)  
    6. {  
    7.     int len_s = strlen(src);  
    8.     int len_d = strlen(des);  
    9.     int next[26] = {0};  
    10.     for (int j = 0; j < 26; ++j)  
    11.         next[j] = len_d + 1;  
    12.     for (int j = 0; j < len_d; ++j)  
    13.         next[des[j] - 'a'] = len_d - j; //记录字符到最右段的最短距离+1  
    14.     //例如:des = "abcedfb"  
    15.     //next = {7 1 5 4 3 2 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8}  
    16.     int pos = 0;  
    17.     while (pos < (len_s - len_d + 1)) //末端对齐  
    18.     {  
    19.         int i = pos;  
    20.         int j;  
    21.         for (j = 0; j < len_d; ++j, ++i)  
    22.         {  
    23.             if (src[i] != des[j])  
    24.             {  
    25.                 pos += next[src[pos + len_d] - 'a'];  
    26.                 //不等于就跳跃,跳跃是核心  
    27.                 break;  
    28.             }  
    29.         }  
    30.         if ( j == len_d )  
    31.             return pos;  
    32.     }  
    33.     return -1;  
    34. }  
    35.   
    36.   
    37. int main()  
    38. {  
    39.     char src[]="abcdacdaahfacabcdabcdeaa";  
    40.     char des[]="abcde";  
    41.     cout<<sunday(src,des)<<endl;  
    42.     return 0;  
    43. }  
     

    ╝⑤ 

     

    Boyer-Moore、Horspool、Sunday算法小结

                   Boyer-Moore、Horspool、Sunday算法都是基于后缀数组的匹配算法,区别在于移动的方式不一样(好像网上有些都没有说的Boyer-Moore算法的好后缀规则,有可能是优化方法吧,没有去深究,抱歉)。下面给出三种方法的对比:

    0 1 2 3 4 5 6 7 8 9 ...
    abcabdaacba
    bcaab      
     bcaab     
     0 1 2 3 4 5 6 7 8 9 ...
    abcabdaacba
    bcaab      
        bcaab  
     0 1 2 3 4 5 6 7 8 9 ...
    abcabdaacba
    bcaab      
          bcaab
         
    (a)   Boyer-Moore (b)   Horspool (c)   Sunday
         

     

    In this example, t0, ..., t4 =  a b c a b is the current text window that is compared with the pattern. Its suffix a b has matched, but the comparison c-a causes a mismatch. The bad-character heuristics of the Boyer-Moore algorithm (a) uses the "bad" text character c to determine the shift distance. The Horspool algorithm (b) uses the rightmost character b of the current text window. The Sunday algorithm (c) uses the character directly right of the text window, namely d in this example. Since d does not occur in the pattern at all, the pattern can be shifted past this position.

    ╝⑥

    §4 Knuth-Morris-Pratt(KMP)算法

    KMP算法是一种高效的前缀匹配算法,在传统蛮力(BF)匹配算法的基础上改进的地方在于每次移动的距离不是1可以是更大,没有进行回溯,BF算法的时间复杂度是O(m*n),而KMP算法的时间复杂度是O(m+n)。

    假设执行第i+1趟匹配时,如果比较模式串P中的第j个字符时不匹配,也就是有

    T[i,i+1,...,i+j-1]=P[0,1,...,j-1],T[i+j]≠P[j]  (打不了下标,就有数组的形式给出字符串)   (1)

    BF算法下一趟是从目标的第i+1位置开始与模式串比较。如果匹配成功则有

    T[i+1,i+2,...,i+m]=P[0,1,...m-1]                               (2)

    如果模式串P有如下特征

    P[0,1,...j-2]=P[1,2,...j-1]                     (3)

    由(1)可知

    T[i+1,i+2,...,i+j+1]=P[1,2,...j-1]                               (4)

    由(3)(4)可知

    T[i+1,i+2,...,i+j+1]≠P[0,1,...j-2]                               (5)

    故由

     

    T[i+1,i+2,....,i+m]≠P[0,1,...m-1]

    所以第i+2趟是匹配可以不需要进行,因为一定不能匹配。

    类似可以推得

    P[0,1,...k-1]=P[j-k-1,j-k,...j-1]

    这时才有

    P[0,1,...k-1]=P[j-k-1,j-k,...j-1]=T[i+j-k,i+j-k+1,i+j-1]

    模式串P从当前位置直接向右移动 j-k 位置,使模式串P的第 k 个字符P[k]与目标串T中的第i+j个字符对齐开始比较(前面 k 个已经匹配)。

    造成BF算法效率低的主要原因是在算法执行过程中有回溯,而这些回溯是可以避免的。KMP算法的关键是在匹配失败时,确定下一次匹配的位置,设next[j]=k,表示当模式串P中第j个字符与母串T相应字符不匹配时,模式串P中应当由第K个字符与目标串中刚不匹配的字符对齐继续进行比较。

    例如,模式串P="abaabcac",其对应的next[j]如下:

     

     

    i

    0

    1

    2

    3

    4

    5

    6

    7

    t[i]

    a

    b

    d

    a

    b

    c

    d

    e

    next[i]

    -1

    0

    0

    0

    1

    2

    0

    0

     

     

    next数组构造

                              ╔   -1,   j=0;

                next[j]=         ║max{k| 0<k<j 且 P[0,1,...,k-1]=P[j-k,j-k+1,..j-1}

                                      ╚    0,    其他情况

    next数组求解是一个递推过程,

    设next[j]=k,则有

    P[0,1,...k-1]=P[j-k,j-k+1,...,j-1]

     

                next[j]=         ╔ max{k| 0<k<j 且 P[0,1,...,k]=P[j-k,j-k+1,..j-1}

                                      ╚    0,    其他情况

    如果P[k]=P[j],有 next[j+1]=next[j]+1=k+1。

    如果P[k]≠P[j],有 P[0,1,...,k]≠P[j-k,j-k+1,...j],

    假设next[j+1]=h+1,则有下式成立

    P[0,1,...h]=P[j-h+1,j-k+1,...j]    P[h]=P[j]

    又因为

    P[0,1,...h-1]=P[j-h,j-k+1,...j-1]=P[k-h,k-h+1,k-1]    (next[k]=h的情况)

    即此时实际只需要满足 next[k]=h(前面已经求解过)时,P[h]=P[j] 就有next[j+1]=h+1,否则(不存在这样的h)next[j+1]等于0。

    由此可以得到计算next的递推公式

     

    KMP算法实现

     

    C代码   收藏代码
    1.  /* ******************************************************************* 
    2.     created:    2006/07/02 
    3.     filename:     KMP.cpp 
    4.     author:        李创 
    5.                  http://www.cppblog.com/converse/  
    6.                  
    7.                 参考资料: 严蔚敏<<数据结构>> 
    8.  
    9.     purpose:    KMP字符串匹配算法的演示 
    10. ******************************************************************** */   
    11.    
    12. #include  < stdio.h >   
    13. #include  < stdlib.h >   
    14. #include  < assert.h >   
    15. #include  < string .h >   
    16.    
    17.  #define  MAX_LEN_OF_STR    30             //  字符串的最大长度   
    18.    
    19. typedef  struct  String                 //  这里需要的字符串数组,存放字符串及其长度   
    20.  {  
    21.      char     str[MAX_LEN_OF_STR];     //  字符数组   
    22.       int         length;                     //  字符串的实际长度   
    23.  } String,  * PString;  
    24.   
    25.  //  得到字符串的next数组   
    26.  void  GetNextArray(PString pstr,  int  next[])  
    27.  {  
    28.     assert(NULL  !=  pstr);   
    29.     assert(NULL  !=  next);  
    30.     assert(pstr -> length  >   0 );  
    31.   
    32.      //  第一个字符的next值是-1,因为C中的数组是从0开始的   
    33.      next[ 0 ]  =   - 1 ;  
    34.      for  ( int  i  =   0 , j  =   - 1 ; i  <  pstr -> length  -   1 ; )  
    35.      {  
    36.          //  i是主串的游标,j是模式串的游标  
    37.          //  这里的主串和模式串都是同一个字符串   
    38.           if  ( - 1   ==  j  ||                          //  如果模式串游标已经回退到第一个字符   
    39.              pstr -> str[i]  ==  pstr -> str[j])     //  如果匹配成功   
    40.           {  
    41.              //  两个游标都向前走一步   
    42.               ++ i;  
    43.              ++ j;  
    44.              //  存放当前的next值为此时模式串的游标值   
    45.              next[i]  =  j;  
    46.         }   
    47.          else                                  //  匹配不成功j就回退到上一个next值   
    48.           {  
    49.             j  =  next[j];  
    50.         }   
    51.     }   
    52. }   
    53.    
    54.  //  KMP字符串模式匹配算法  
    55.  //  输入: S是主串,T是模式串,pos是S中的起始位置  
    56.  //  输出: 如果匹配成功返回起始位置,否则返回-1   
    57.  int  KMP(PString S, PString T,  int  pos)  
    58.  {  
    59.     assert(NULL  !=  S);  
    60.     assert(NULL  !=  T);  
    61.     assert(pos  >=   0 );  
    62.     assert(pos  <  S -> length);  
    63.       
    64.      if  (S -> length  <  T -> length)  
    65.          return   - 1 ;  
    66.   
    67.     printf( " 主串\t = %s\n " , S -> str);  
    68.     printf( " 模式串\t = %s\n " , T -> str);  
    69.   
    70.      int   * next  =  ( int   * )malloc(T -> length  *   sizeof ( int ));  
    71.      //  得到模式串的next数组   
    72.      GetNextArray(T, next);  
    73.   
    74.      int  i, j;  
    75.      for  (i  =  pos, j  =   0 ; i  <  S -> length  &&  j  <  T -> length; )  
    76.      {  
    77.          //  i是主串游标,j是模式串游标   
    78.           if  ( - 1   ==  j  ||                  //  模式串游标已经回退到第一个位置   
    79.              S -> str[i]  ==  T -> str[j])  //  当前字符匹配成功   
    80.           {  
    81.              //  满足以上两种情况时两个游标都要向前进一步   
    82.               ++ i;  
    83.              ++ j;  
    84.         }   
    85.          else                          //   匹配不成功,模式串游标回退到当前字符的next值   
    86.           {  
    87.             j  =  next[j];  
    88.         }   
    89.     }   
    90.    
    91.     free(next);  
    92.   
    93.      if  (j  >=  T -> length)  
    94.      {  
    95.          //  匹配成功   
    96.           return  i  -  T -> length;  
    97.     }   
    98.      else   
    99.       {  
    100.          //  匹配不成功   
    101.           return   - 1 ;  
    102.     }   
    103. }  

    ╝③ 

    §5 Karp-Rabin(KR)算法

     

    Karp-Rabin算法是利用hash函数的特性进行字符串匹配的。 KR算法对模式串和循环中每一次要匹配的子串按一定的hash函数求值,如果hash值相同,才进一步比较这两个串是否真正相等。

    Karp-Rabin算法适用于多个字符串匹配较好。

    §6 Aho-Corasick算法

     

    Aho-Corasick算法又叫AC自动机算法,是一种多模式匹配算法。Aho-Corasick算法可以在目标串查找多个模式串,出现次数以及出现的位置。

    Aho-Corasick算法原理

    Aho-Corasick算法主要是应用有限自动机的状态转移来模拟字符的比较,下面对有限状态机做几点说明:


    上图是由多模式串{he,she,his,hers}构成的一个有限状态机:

    1.该状态当字符匹配是按实线标注的状态进行转换,当所有实线路径都不满足(即下一个字符都不匹配时)按虚线状态进行转换。

    2.对ushers匹配过程如下图所示:

     

    当转移到红色结点时表示已经匹配并且获得模式串

    Aho-Corasick算法步骤

    Aho-Corasick算法和前面的算法一样都要对模式串进行预处理,预处理主要包括字典树Tire的构造,构建状态转移表(goto),失效函数(failure function),输出表(Output)。

    Aho-Corasick算法包括以下3个步骤

    1.构建字典树Tire

    2.构建状态转移表,失效函数(failure function),输出表(Output)

    3.搜索路径(进行匹配)

    下面3个步骤分别进行介绍

    构建字典树Tire

    Tire是哈希树的变种,Tire树的边是模式串的字符,结点就是Tire的状态表,下图是多模式串{he,she,his,hers}的Tire树结构:

     

    构建goto函数、failure function和Output函数                                                                                                                                                                                                

           goto函数(状态转移函数):goto(pre,v)=next,完成这样的任务:在当前状态pre,输入字符v,得到下一个状态next,如果没有下个状态则next=failure。                                                      

           failure function:失效函数是处理当前状态是failure时的处理。                                                                                                                                                                                    

          output函数:当完成匹配是根据状态输出匹配的模式串。

     

    下面是多模式串{he,she,his,hers}的goto函数,failure函数,output函数

    goto函数:


    failure函数

    output函数

     

    多模式串{he,she,his,hers}最终的有限状态机图

     

    Aho-Corasick算法实现

     

     

    C代码   收藏代码
    1.     
    2. /*  
    3. 程序说明:多模式串匹配的AC自动机算法  
    4. 自动机算法可以参考《柔性字符串匹配》里的相应章节,讲的很清楚  
    5. */    
    6. #include <stdio.h>    
    7. #include <string.h>    
    8.      
    9.      
    10. const int MAXQ = 500000+10;    
    11. const int MAXN = 1000000+10;    
    12. const int MAXK = 26; //自动机里字符集的大小    
    13. struct TrieNode    
    14. {    
    15.        TrieNode* fail;    
    16.        TrieNode* next[MAXK];    
    17.        bool danger;   //该节点是否为某模式串的终结点    
    18.        int cnt;    //以该节点为终结点的模式串个数    
    19.        TrieNode()    
    20.        {    
    21.               fail = NULL;    
    22.               memset(next, NULL, sizeof(next));    
    23.               danger = false;    
    24.               cnt = 0;    
    25.        }    
    26. }*que[MAXQ], *root;    
    27. //文本字符串    
    28. char msg[MAXN];    
    29. int   N;    
    30. void TrieInsert(char *s)    
    31. {    
    32.        int i = 0;    
    33.        TrieNode *ptr = root;    
    34.        while(s[i])    
    35.        {    
    36.               int idx = s[i]-'a';    
    37.               if(ptr->next[idx] == NULL)    
    38.                      ptr->next[idx] = new TrieNode();    
    39.               ptr = ptr->next[idx];    
    40.               i++;    
    41.        }    
    42.        ptr->danger = true;    
    43.        ptr->cnt++;    
    44. }    
    45.      
    46. void Init()    
    47. {    
    48.        int i;    
    49.        char s[100];    
    50.        root = new TrieNode();    
    51.        scanf("%d", &N);    
    52.        for(i = 0; i < N; i++)    
    53.        {    
    54.               scanf("%s", s);    
    55.               TrieInsert(s);    
    56.        }    
    57. }    
    58.      
    59. void Build_AC_Automation()    
    60. {    
    61.        int rear = 1, front = 0, i;    
    62.        que[0] = root;    
    63.        root->fail = NULL;    
    64.        while(rear != front)    
    65.        {    
    66.               TrieNode *cur = que[front++];    
    67.               for(i = 0; i < 26; i++)    
    68.                      if(cur->next[i] != NULL)    
    69.                      {    
    70.                             if(cur == root)    
    71.                                    cur->next[i]->fail = root;    
    72.                             else    
    73.                             {    
    74.                                    TrieNode *ptr = cur->fail;    
    75.                                    while(ptr != NULL)    
    76.                                    {    
    77.                                           if(ptr->next[i] != NULL)    
    78.                                           {    
    79.                                                  cur->next[i]->fail = ptr->next[i];    
    80.                                                  if(ptr->next[i]->danger == true)    
    81.                                                         cur->next[i]->danger = true;    
    82.                                                  break;    
    83.                                           }    
    84.                                           ptr = ptr->fail;    
    85.                                    }    
    86.                                    if(ptr == NULL) cur->next[i]->fail = root;    
    87.                             }    
    88.                             que[rear++] = cur->next[i];    
    89.                      }    
    90.        }    
    91. }    
    92. int AC_Search()    
    93. {    
    94.        int i = 0, ans = 0;    
    95.        TrieNode *ptr = root;    
    96.        while(msg[i])    
    97.        {    
    98.               int idx = msg[i]-'a';    
    99.               while(ptr->next[idx] == NULL && ptr != root) ptr = ptr->fail;    
    100.               ptr = ptr->next[idx];    
    101.               if(ptr == NULL) ptr = root;    
    102.               TrieNode *tmp = ptr;    
    103.               while(tmp != NULL && tmp->cnt != -1)    
    104.               {    
    105.                      ans += tmp->cnt;    
    106.                      tmp->cnt = -1;    
    107.                      tmp = tmp->fail;    
    108.               }    
    109.               i++;    
    110.        }    
    111.        return ans;    
    112. }    
    113. int main()    
    114. {    
    115.        int T;    
    116.        scanf("%d", &T);    
    117.        while(T--)    
    118.        {    
    119.               Init();    
    120.               Build_AC_Automation();    
    121.               //文本    
    122.               scanf("%s", msg);    
    123.               printf("%d\n", AC_Search());    
    124.        }    
    125.     return 0;    
    126. }   

     

     

     

    §7 小结

           这篇文章把字符串匹配的六个算法——BM、Horspool、Sunday、KMP、KR、AC算法,从原理到步骤,再从流程到实现都做了讲解了,能有了一定的认识和理解,基本可以掌握这些算法。如果你有任何建议或者批评和补充,请留言指出,不胜感激,更多参考请移步互联网。

     

    参考(后面3个链接很不错的哟):

    ①jijy:http://www.searchtb.com/2011/07/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E9%82%A3%E4%BA%9B%E4%BA%8B%EF%BC%88%E4%B8%80%EF%BC%89.html

    ②ouyangjia7:http://ouyangjia7.iteye.com/blog/353137

    那谁的技术博客http://www.cppblog.com/converse/archive/2006/07/05/9447.html

    CobbLiuhttp://www.cnblogs.com/cobbliu/archive/2012/05/29/2524244.html

    ⑤kmplayer:http://kmplayer.iteye.com/blog/704187

    ⑥志文工作室:http://www.zhiwenweb.cn/Category/Security/1274.htm

    http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm

    http://www-igm.univ-mlv.fr/~lecroq/string/

    http://www.csie.ntnu.edu.tw/~u91029/StringMatching.html

    展开全文
  • 字符串模式匹配算法的 Java 实现

    千次阅读 2019-02-21 20:28:39
    字符串匹配算法:检查模式P是否另一个字符T(T代表文本)的子串,因为要检查整个定长的字符P,所以有时这些算法称为精确字符串匹配算法。 蛮力法(BF算法) 对于文本T中的每个可能的位置,检查P是否匹配,...

    字符串匹配算法

      检查模式P是否另一个字符串T(T代表文本)的子串,因为要检查整个定长的字符串P,所以有时这些算法称为精确字符串匹配算法。此算法通常输入为原字符串(string)和子串(pattern),要求返回子串在原字符串中首次出现的位置。比如原字符串为“ABCDEFG”,子串为“DEF”,则算法返回3。常见的算法包括:BF(Brute Force,暴力检索)、RK(Robin-Karp,哈希检索)、KMP(教科书上最常见算法)、BM(Boyer Moore)、Sunday等,下面实现BF和KMP算法。

    1. 蛮力法(BF算法)

    对于文本T中的每个可能的位置,检查P是否匹配,由于文本T的长度为n,模式P的长度m, 所以T的最后m -1个位置无需检查,即有n-m+1个可选的位置来比较。

    /**
    	 * 搜索模式字符串P在文本字符串T中第一次出现的位置的蛮力解法
    	 * 对于文本T中的每个可能的位置,检查P是否匹配,由于文本T的长度为n,模式P的长度为m,
    	 * 所以T的最后m - 1个位置无需检查,即有n-m+1个可选的位置来比较。
    	 * @param T
    	 * @param P
    	 * @return
    	 */
    	private static int[] F;
    	public static int bruteForceStringMatch(String T, String P) {
    		char[] t = T.toCharArray();
    		char[] p = P.toCharArray();
    		int n = t.length;
    		int m = p.length;
    		
    		for(int i = 0; i < n - m + 1; i ++) {
    			int j = 0;
    			while(j < m && p[j] == t[i + j])
    				j++;
    			if(j == m) {
    				return i;
    			}				
    		}	
    		return -1;
    	}
    

    时间复杂度为O((n-m+1)m)=O(nm)
    空间复杂度为O(1)

    2. RK算法:

    RK算法是对BF算法的一个改进:在BF算法中,每一个字符都需要进行比较,并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中,就尝试只进行一次比较来判定两者是否相等。
    RK算法也可以进行多模式匹配,在论文查重等实际应用中一般都是使用此算法。
    这里写图片描述
    首先计算子串的HASH值,之后分别取原字符串中子串长度的字符串计算HASH值,比较两者是否相等:如果HASH值不同,则两者必定不匹配,如果相同,由于哈希冲突存在,也需要按照BF算法再次判定。
    按照此例子,首先计算子串“DEF”HASH值为Hd,之后从原字符串中依次取长度为3的字符串“ABC”、“BCD”、“CDE”、“DEF”计算HASH值,分别为Ha、Hb、Hc、Hd,当Hd相等时,仍然要比较一次子串“DEF”和原字符串“DEF”是否一致。
    时间复杂度:最坏情况:O(MN),最好情况:O(m+n)

    3. KMP算法

    我们来观察一下朴素的字符串匹配算法的操作过程。如下图(a)中所描述,在模式 P = ababaca 和文本 T 的匹配过程中,模板的一个特定位移 s,q = 5 个字符已经匹配成功,但模式 P 的第 6 个字符不能与相应的文本字符匹配。

    在这里插入图片描述

    此时,q 个字符已经匹配成功的信息确定了相应的文本字符,而知道这 q 个文本字符,就使我们能够立即确定某些位移是非法的。例如上图(a)中,我们可以判断位移 s+1 是非法的,因为模式 P 的第一个字符 a 将与模式的第二个字符 b 匹配的文本字符进行匹配,显然是不匹配的。而图(b)中则显示了位移 s’ = s+2 处,使模式 P 的前三个字符和相应的三个文本字符对齐后必定会匹配。KMP 算法的基本思路就是设法利用这些已知信息,不要把 “搜索位置” 移回已经比较过的位置,而是继续把它向后面移,这样就提高了匹配效率。

    怎么做到利用这些已知信息呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。
    首先,要了解两个概念:“前缀"和"后缀”。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

    "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,

        "A"的前缀和后缀都为空集,共有元素的长度为0;
    
     "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
    
     "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
    
     "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
    
     "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;
    
     "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;
    
     "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。
    

    "部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,“ABCDAB"之中有两个"AB”,那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

    package com.wuyi.notecode;
    
    public class KMP {
    
        private int[] next;
    
        public int KMP(String T, String P){
            // 先构造 next 数组
            createNext(P);
    
            for(int i = 0, j = 0; i < T.length();){
                if (j == P.length() - 1)
                    return i - j;
    
                if (j == 0 || T.charAt(i) == P.charAt(j)){
                    i++;
                    j++;
                } else {
                    j = next[j];
                }
            }
            return -1;
        }
    
        private void createNext(String P) {
            next = new int[P.length()];
            next[0] = 0;
    
            for (int i = 1, j = 0;i < P.length();){
                if (j == 0 || P.charAt(i - 1) == P.charAt(j - 1)){
                    //j - 1 代表前缀的最后一个索引,i - 1 代表后缀的最后一个索引
                    next[i] = j;
                    i++;
                    j++;
                } else {
                    // 若字符不相等,则 j 值回溯
                    j = next[j];
                }
            }
        }
    
        public static void main(String[] args) {
            KMP kmp = new KMP();
            int res = kmp.KMP("baabcabxaababaaabaab","ababaaaba");
            for (int a : kmp.next){
                System.out.print(a + " ");
            }
            System.out.println("\nres:" + res);
        }
    }
    
    

    注意:

    • KMP算法从左向右比较
    • KMP算法需要一个时间和空间开销为O(m)的预处理(部分匹配函数)过程
    • 匹配查找的时间复杂度为O(n+m)

    4. KMP模式匹配算法的改进

      它是在计算 next 值的同时,如果a位字符与 next[i] 值指向对的b位字符相等,则该a位的 next[i] 就指向 b 位的 next[i] 值,如果不等,则该 a 位的 next[i] 值就是它自己 a 位的 next[i] 值。

    package com.wuyi.notecode;
    
    public class KMP {
    
        private int[] next;
    
        public int KMP(String T, String P){
            // 先构造 next 数组
            createNext(P);
    
            for(int i = 0, j = 0; i < T.length();){
                if (j == P.length() - 1)
                    return i - j;
    
                if (j == 0 || T.charAt(i) == P.charAt(j)){
                    i++;
                    j++;
                } else {
                    j = next[j];
                }
            }
            return -1;
        }
    
        private void createNext(String P) {
            next = new int[P.length()];
            next[0] = 0;
    
            for (int i = 1, j = 0;i < P.length();){
                if (j == 0 || P.charAt(i - 1) == P.charAt(j - 1)){
                    //j - 1 代表前缀的最后一个索引,i - 1 代表后缀的最后一个索引
                    //next[i] = j;
                    if (P.charAt(i) != P.charAt(j))
                        next[i] = j;
                    else
                        next[i] = next[j];
                    i++;
                    j++;
                } else {
                    // 若字符不相等,则 j 值回溯
                    j = next[j];
                }
            }
        }
    
        public static void main(String[] args) {
            KMP kmp = new KMP();
            int res = kmp.KMP("baabcabxaababaaabaab","abaaba");
            for (int a : kmp.next){
                System.out.print(a + " ");
            }
            System.out.println("\nres:" + res);
        }
    }
    
    
    展开全文
  •  Boyer-Moore算法是基于后缀匹配的模式串匹配算法模式串的匹配是从右向左的,但模式串的移动依然是从从左向右移动。关于如何高效的移动模式串,Boyer-Boore定义了两个规则:坏字符规则与好后缀规则。如下图:  ...

    Boyer-Moore(BM)算法原理

        Boyer-Moore算法是基于后缀匹配的模式串匹配算法,模式串的匹配是从右向左的,但模式串的移动依然是从从左向右移动。关于如何高效的移动模式串,Boyer-Boore定义了两个规则:坏字符规则与好后缀规则。如下图:

       

     坏字符规则:

    1. 如果坏字符没有出现在模式串中,直接将模式串移到坏字符对应的下一个字符对应的位置。如图c为坏字符,没有出现在模式串P中,直接将P移到c的下一个位置。


           2.如果坏字符出现在模式串中,则需要将模式串中最靠近好后缀的坏字符与母串的坏字符对齐(后面的代码并没有实现这一步)。


    好后缀规则:

            1.  模式串中有子串与好后缀匹配,此时移动模式串,让该子串与母串中的好后缀对齐即可;如果模式串中有多个子串与好后缀匹配,则选择最靠近好后缀的子串对齐即可。

            2.  模式串中没有子串匹配上好后缀,此时需要寻找模式串中的一个最长前缀,并让该前缀等于好后缀的后缀。寻找到该前缀后,让该前缀与好后缀的后缀对齐即可。

            3.  模式串中找不到子串与好后缀匹配,同时也找 不到最长前缀,让该前缀与好后缀的后缀匹配。此时,移动模式串与母串中好后缀的下一个字符对齐即可。

    Boyer-Moore算法步骤

     

    1.对模式子串进行预处理

     

    Boyer-Moore算法实现必须对模式串进行预处理,得到坏字符规则和好后缀规则移动的映射表,下面代码中MakeSkip是建立坏字符规则移动的映射表,MakeShift是建立好后缀规则的移动映射表。

    MakeSkip是构造数组skip[],skip[k]表示字符k距离模式串末尾的距离。

    MakeShfit是构造数组shfit[],shfit[k]表示模式串的以位置k为边界的后缀子串的最靠近的模式子串(或最前缀子串)到模式子串末尾的距离,例如:abcab,shfit[3]=3和shfit[2]=3(即都是第一个b到末尾的距离),k=2时,后缀子串为cab,这时只有最长前缀ab,shfit[2]=3。

    2.从b_idx开始查找,得到坏字符和好后缀,得到最大移动距离,移动b_idx,直至b_idx到达母串的末尾。

     

     

    Boyer-Moore算法实现

    /*
        函数:int* MakeSkip(char *, int)
    	目的:根据坏字符规则做预处理,建立一张坏字符表
    	参数:
    		ptrn => 模式串P
    		PLen => 模式串P长度
        返回:
    	    int* - 坏字符表
    */
    int* MakeSkip(char *ptrn, int pLen)
    {	
    	int i;
    	//为建立坏字符表,申请256个int的空间
    	/*PS:之所以要申请256个,是因为一个字符是8位,
    	  所以字符可能有2的8次方即256种不同情况*/
    	int *skip = (int*)malloc(256*sizeof(int));
    
    	if(skip == NULL)
    	{
    		fprintf(stderr, "malloc failed!");
    		return 0;
    	}	
    
    	//初始化坏字符表,256个单元全部初始化为pLen,没有在模式串出现的字符距离为pLen。
    	for(i = 0; i < 256; i++)
    	{
    		*(skip+i) = pLen;
    	}
    
    	//给表中需要赋值的单元赋值,不在模式串中出现的字符就不用再赋值了
    	while(pLen != 0)
    	{
    		*(skip+(unsigned char)*ptrn++) = pLen--;
    	}
    
    	return skip;
    }
    
    
    /*
    	函数:int* MakeShift(char *, int)
    	目的:根据好后缀规则做预处理,建立一张好后缀表
    	参数:
    		ptrn => 模式串P
    		PLen => 模式串P长度
        返回:
    	    int* - 好后缀表
    */
    int* MakeShift(char* ptrn,int pLen)
    {
    	//为好后缀表申请pLen个int的空间
    	int *shift = (int*)malloc(pLen*sizeof(int));
    	int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标
    	char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标
    	char c;
    
    	if(shift == NULL)
    	{
    		fprintf(stderr,"malloc failed!");
    		return 0;
    	}
    
    	c = *(ptrn + pLen - 1);//保存模式串中最后一个字符,因为要反复用到它
    
    	*sptr = 1;//以最后一个字符为边界时,确定移动1的距离
    
    	pptr--;//边界移动到倒数第二个字符(这句是我自己加上去的,因为我总觉得不加上去会有BUG,大家试试“abcdd”的情况,即末尾两位重复的情况)
    
    	while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作
    	{
    		char *p1 = ptrn + pLen - 2, *p2,*p3;
    		
    		//该do...while循环完成以当前pptr所指的字符为边界时,要移动的距离
    		do{
    			while(p1 >= ptrn && *p1-- != c);//该空循环,寻找与最后一个字符c匹配的字符所指向的位置
    			
    			p2 = ptrn + pLen - 2;
    			p3 = p1;
    			
    			while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//该空循环,判断在边界内字符匹配到了什么位置
    
    		}while(p3 >= ptrn && p2 >= pptr);
    
    		*sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中,以pptr所在字符为边界时,要移动的位置
    		/*
    		  PS:在这里我要声明一句,*sptr = (shift + pLen - sptr) + p2 - p3;
    		     大家看被我用括号括起来的部分,如果只需要计算字符串移动的距离,那么括号中的那部分是不需要的。
    			 因为在字符串自左向右做匹配的时候,指标是一直向左移的,这里*sptr保存的内容,实际是指标要移动
    			 距离,而不是字符串移动的距离。我想SNORT是出于性能上的考虑,才这么做的。			 
    		*/
    
    		pptr--;//边界继续向前移动
    	}
    
    	return shift;
    }
    
    
    /*
    	函数:int* BMSearch(char *, int , char *, int, int *, int *)
    	目的:判断文本串T中是否包含模式串P
    	参数:
    	    buf => 文本串T
    		blen => 文本串T长度
    		ptrn => 模式串P
    		PLen => 模式串P长度
    		skip => 坏字符表
    		shift => 好后缀表
        返回:
    	    int - 1表示成功(文本串包含模式串),0表示失败(文本串不包含模式串)。
    */
    int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
    {
    	int b_idx = plen;  
    	if (plen == 0)
    		return 1;
    	while (b_idx <= blen)//计算字符串是否匹配到了尽头
    	{
    		int p_idx = plen, skip_stride, shift_stride;
    		while (buf[--b_idx] == ptrn[--p_idx])//开始匹配
    		{
     			if (b_idx < 0)
    				return 0;
    			if (p_idx == 0)
    			{     
    				return 1;
    			}
    		}
    		skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳跃的距离
    		shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离
    		b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
    	}
    	return 0;
    }



    展开全文
  • 模式匹配算法

    千次阅读 2019-06-16 16:32:07
    最近在学数据结构中的,现在来写一写我对的不同模式匹配算法的理解: 声明:首先需要注意这里面的的存储结构,它并不是普通的像C语言中的字符一样在每个末尾有一个结尾标志‘/0’,然而这里是通过在数组...

    最近在学数据结构中的串,现在来写一写我对串的不同模式匹配算法的理解:
    声明:首先需要注意这里面的串的存储结构,它并不是普通的像C语言中的字符串一样在每个串末尾有一个结尾标志‘/0’,然而这里是通过在数组下标为0的元素赋值为整个串的有效长度值,例如字符串friend,储存它的数组最后一个元素T[6]中存储字符’d’;第一个元素T[0]存储有效长度6;第一个存储字符的元素T[1]存储的字符’f’。然后需要注意的是这里所说的有效长度的问题,这里字符的储存都是从下标为1的元素开始,在连续的空间里面。不要理解错了。
    1.朴素的模式匹配算法
    核心思想是:对主串S的每一个字符作为子串的开头,与要匹配的字符串进行匹配,对主串做大循环,每个字符开头做长度为T[0]的小循环,直到匹配成功或全部遍历完成为止。
    下面是对应的代码:

    int Index(String S,STring T,int pos)
    {
     int i=pos;
     int j=1;
     while(i<=S[0]&&j<=T[0])
     {
      if(S[i]==T[j])
      {
       ++i;
       ++j;
      }
      else
      {
       i=i-j+2;
       j=1;
      }
      if(j>T[0])
      {
       return i-T[0];
      }
      else return 0;
     }
    }
    

    解析:
    第一句:

    int Index(String S,STring T,int pos)
    

    这里面:(1)String是定义串的抽象数据结构。
    (2)pos是表示在寻找子串的时候,是从第pos个字符开始往后寻找的。
    (3)也就是说将来要返回的值是子串在主串S中第pos个字符之后的位置。
    ②循环条件

    while(i<=S[0]&&j<=T[0])
    

    因为i大于S[0]时表示的是已经全部遍历并且未找到合条件的子串;j大于T[0]表示的是找到了对应的子串。所以条件该这么写。

     if(S[i]==T[j])
     {
      ++i;
      ++j;
     }
    

    主串中的S[i]与子串中的T[j]相等则继续循环判断下一组。

    else
     {
      i=i-j+2;
      j=1;
     }
    

    否则,i 将退回到上次匹配首位的下一位。这里一定要能够理解

       i=i-j+2;
    

    这一条语句,其实这里可能画图对理解有较好的帮助;但在这里我直接写出我自己的理解:首先需要理解 i-j 一定是主串S中此时与串T相比较的第一个元素之前的一个元素;其实这一点既可以画个图判断一下,也可以自己直接想象出来。
    然后对于 i-j+2 其实就很好理解了,它自然就是S中与T相比较的第一个元素的之后一个元素。

     if(j>T[0])
     {
      return i-T[0];
     }
    

    j>T[0] 表示的是找到满足条件的子串的情况,这在之前已经说过,这里主要是理解下面的语句:

    return i-T[0];
    

    因为最后的S[i]与T[j]相等后,一定会再执行一遍 ++i 与 ++j,所以此时的 i 表示的是在S中与T的所有字符中相等的最后一个字符的下一个位置。那么,它再减去T的长度,就可以得到在S中与T相等的子串的第一个元素的下标,也就是要求的子串T在主串S中的第pos个字符之后的位置。
    2.朴素模式匹配算法的问题:
    例如主串S=abcdefgab 子串T=abcdex;如果用朴素模式匹配算法,第一步:当主串中是从第一个开始进行比较时,会发现前五个元素都对应相等,然后 i 停在了第六个元素,然后执行了 i=i-j+2; 语句后,i 就会回到之前与T中第一个字符相比较的位置的下一个位置,再次执行比较语句 if(S[i]==T[j]) 发现不相等,i 便再一次执行语句 i=i-j+2; 再返回到刚才与T中第一个字符元素相比较的位置的下一个位置。
    然后就这样一直循环判断会发现从S中的第二个字符b开始,一直到第五个字符e,这几个的判断有一个规律:首先bcde自身都与T中第一个字符a不相等;在比较了第一次发现S与T的前5个字符都对应相等,则可以说明T中第一个字符a与S中的bcde也是不相等的!那么也就是说如果我们足够了解T自身的情况的话,在比较了第一次之后面的有些步骤就可以省略,比如这里在第1次循环之后的第2345次循环都是多余的。
    但是由于第一次比较的结果中发现S与T中第6个元素是不相等的,而T自身中第一个字符a与第六个字符x本身也是不相等的,所以由第一次判断之后并不能直接得到T中第一个元素a与S中第6个元素不相等的结论,所以后面的比较就应该从S中的第6个字符开始。
    3.KMP模式匹配算法
    ①先看一个例子:S=“abcababca” ,T=“abcabx”。按照之前的经验,首先比较第一次之后,发现前五个字符都是对应相等的,然后就是T自身的规律是:第一个字符a与后面的第二,三,五个字符不相等,而与第四个字符相等;那么在第一次的比较之后我们就还是可以省略一些步骤:T中a与S中第二,三个字符b,c不相等,则下一次循环可以直接跳过,然后 i 现在来到了4;发现T中一二个字符ab与T中的第4,5个字符相等,所以这1,2个元素在进行了第一次比较的条件下自然也是与S中第4,5个元素相等,所以在进行以S中第4个字符为开头与T进行比较时,前两个比较就可以省略,然后继续比较S中第六个和T中第三个元素。
    也就是说在进行了第一次比较之后,可以省略一些不必要的步骤,然后直接进行到以S中第四个字符开头,并且省略前两步,此时 i 到了6的这里。再依次进行。
    通过之前的讲解我们发现:
    (1)由于第一次的比较一定会使得 i 停在与T中字符不相等的位置,那么此时的 i 之前的各个元素一定是对应相等的,那么我们就可以利用这个相等得到一些信息使算法简化。
    (2)在省略掉不必要的步骤之后,进行下一步时,发现 i 其实是不需要回溯的。
    (3)从T是“abcdex”变到T=“abcabx”,在第二次的比较中,分为j 从1开始和j从3开始两种,并且发现 j的这种变化关键取决于T串的结构中是否有重复的问题。
    因此,为了研究T串自身的特征,引入了一个数组next,下面是它的函数定义:

               0,当j=1时 
    next[j]=Max{k|1<k<j,且'p1...pk-1'='pj-k+1...pj-1'}
               1,当'p1...pj-1'中没有重复的时候
    

    例如子串T=“abcdex”,按照上面的函数定义,推导出next数组的过程如下:
    (1)当j=1时,next[1]=0;
    (2)当j=2时,j由1到j-1 就只有字符“a”,属于第三种情况,'p1…pj-1’中没有重复,所以next[2]=1;
    (3)当j=3时,j由1到j-1 串是“ab",a与b不是相同的字符,还是属于第三中没有重复的情况,所以next[3]=1;
    以后同理,最终此T串的next数组为:011111
    例2:T=“abcabx”
    (1)当j=1时,next[1]=0;
    (2)当j=2时,j由1到j-1 就只有字符“a”,属于第三种情况,‘p1…pj-1’中没有重复,所以next[2]=1;
    (3)当j=3时,j由1到j-1 串是“ab",a与b不是相同的字符,还是属于第三种没有重复的情况,所以next[3]=1;
    (4)当j=4时,j由1到j-1=3,串是“abc”,还是属于第三种没有重复的情况,所以next[4]=1;
    (5)当j=5时,j由1到j-1=4,串是“abca”,此时前缀字符a与后缀字符a相等,即’p1’=‘p4’,所以k-1=1;j-k+1=5-k+1=4都可以得出此时k值为2;
    (6)当j=6时,j由1到j-1=5,串是“abcab”,此时有“p1p2”=“p4p5”,所以k-1=2;或j-k+1=6-k+1=4都可以算出k的值为3
    因此此时的next数组就变为011123
    同时可以总结出经验:如果前后缀一个字符相等,k值是2;如果是两个字符相等,k值是3;前后缀是n个字符相等,则k值是n+1
    例3:T=“ababaaaba”
    (1)当j=1时,next[1]=0;
    (2)当j=2时,j由1到j-1 就只有字符“a”,属于第三种情况,'p1…pj-1’中没有重复,所以next[2]=1;
    (3)当j=3时,j由1到j-1 串是“ab",a与b不是相同的字符,还是属于第三中没有重复的情况,所以next[3]=1;
    (4)当j=4时,j由1到j-1串是“aba”,“p1”=“p3”,根据之前的规律可以知道这里的k值应为2;
    (5)当j=5时,j由1到j-1串是“abab”,“p1p2”=“p3p4”,所以k值为3;
    (6)当j=6时,j由1到j-1串是“ababa”,所以这里"p1p2p3"=“p3p4p5”,所以k值为4;需要注意的是这里的前缀和后缀中有一个相同的字符,第3个字符a;但是在之前的定义中并没有说前缀和后缀是不能重复的,所以不要仅从概念上单纯的认为前缀和后缀一定是一前一后毫无交集的。
    (7)当j=7时,j由1到j-1串是“ababaa”,可以判断出来这里只有一头一尾"a"=“a”,所以k=2;
    (8)当j=8时,j由1到j-1串是“ababaaa”,还是只有"a"=“a”,所以k=2;
    (9)当j=9时,j由1到j-1串是“ababaaab”,此时前缀“ab”与后缀“ab”相等,所以next[9]=3;
    因此得到的next数组就是:011234223
    例4:T=“aaaaaaaab”
    (1)当j=1时,next[1]=0;
    (2)当j=2时,j由1到j-1 就只有字符“a”,属于第三种情况,'p1…pj-1’中没有重复,所以next[2]=1;
    (3)当j=3时,j由1到j-1串是“aa”,前缀字符“a“与后缀字符”a“相等,next[3]=2;
    (4)当j=4时,j由1到j-1的串是“aaa”,前缀字符是"aa"后缀字符是“aa”,两者相等,next[4]=3;
    (5)…同理可得j=5到j=9时,每一个j值对应的next[j]对应的值,分别为4~8;
    所以数组next中存的值就为012345678
    说明:这里举了4个例子,每一个例子都对应一种特殊的情况,并不是说只要掌握了前面的next[j]函数的计算方法就可以理解它的作用;这里的四个例子都很特殊,需要借助它们来理解短短的几行代码就实现了这个next[j]值的求法的原理。所以这里绝对不是无端的重复。
    另外,严格按照next函数自身的定义来推导next[j]值,对理解它的作用是有帮助的,不要认为一些格式上的东西是没有必要的。
    ②现在来看用代码实现next数组的推导:
    ~~~
    void get_next(String T,int *next)
    {
    int i,j;
    i=1;
    j=0;
    next[1]=0;
    while(i<T[0])
    {
    if(j==0||T[i]==T[j])
    {
    i=i+1;
    next[i]=(j=j+1);
    }
    else
    {
    j=next[j];
    }
    }
    }
    ~~~
    解析:
    (1)首先下面几句:

     i=1;
    j=0;
    next[1]=0;
    

    很容易看出来这是在初始化i和j,并且在为next数组中的next[1]赋值,因为所有的next[1]都为0,所以直接赋值即可,为什么不交给下面的循环来实现呢?可以代入试一下,发现满足判断条件j==0,于是执行下面的语句,结果是next[2]=1;然后再仔细看语句本身,会发现在执行next[i]=j;之前都会有语句i=i+1;而且初始化i=1;所以直接带入循环就会缺少给next[1]赋值为0的过程。
    然后来看i的变化,i 表示的是next数组中的每个元素的下标,所以i 是需要从1开始依次递增的,并且是在每一次需要计入数据的时候加1
    再来看j :j 的含义很丰富
    (1)首先为了后面的表述,需要申明每一次循环得到的i 和j;注意这里指的是

    if(j==0||T[i]==T[j])
     {
      i=i+1;
      next[i]=(j=j+1);
     }
    

    这一步循环,也就是说这里的j值并不是回溯得到的。那么此时的j 值(未进入到if语句中的j值)就表示的是T[i] (i表示的是已进入到if 语句中执行了i+1的语句)之前的字符串中前缀和后缀相等的字符的个数。
    然后如果满足if 的判断语句“T[i]==T[j]”(i和j都是未执行if 下面的语句)再执行语句: i=i+1; next[i]=(j=j+1); 就可以发现它正是在按照next函数的定义来为每个next数组的元素赋值。即每个next[j]元素的值就是T中第j个元素之前的字符串中前缀与后缀相等的元素个数加上1的值。
    这就是j 的第一个含义。

    然后j 的第二个含义是用来理解j 的回溯语句:j=next[j];
    例如字符串“abcabcabxy”当i=9时,j=6,然后执行if的判断语句发现没有满足条件,于是开始执行else语句,然后就会发现j 的值在第一步从6变到3;并且再看j=3时,指向的正是第一个c,并且如果字符串换为“abcabcabcabxy” i=12,j=9,也是执行else部分,然后j的值就会从9变到6,再退回到3;并且指向的也是第一个c;然后再观察这个9,6,3的变化会发现都是“一组”字符串的最后一个,“一组“表示的是像abcabcabc中的abc或abababab中的ab这样的一个字符串重复基础串。并且此时在两个字串“abcabcabxy”和“abcabcabcabxy” 中的x也都在“基础串”的最后一个位置,这是不是说明它每次退回的位置都是前一个”基础串“中与x在自身所在”基础串“中相同的位置呢?
    可以在作相同的举例:串为“abcabcabcax”,i=11,j=8进行if 语句的判断后,发现不满足条件,然后就执行else语句,5=j=next[8],然后2=j=next[5];最后一步回溯先不看,后面再讲;然后就可以直接证明出之前的结论是正确的:它每次退回的位置都是前一个”基础串“中与x在自身所在”基础串“中相同的位置。
    那么究竟为什么就会这样呢?下面开始分析它的成因:
    串“abcdeabcdeabcdxy”

    i=1,   j=0,  next[1]=0;
    i=2,   j=1,  next[2]=1;
          j=0,  
    i=3,   j=1,  next[3]=1;
          j=0,  
    i=4,   j=1,  next[4]=1; 
          j=0,  
    i=5,   j=1,  next[5]=1; 
          j=0,
    i=6,   j=1,  next[6]=1;
    i=7,   j=2,  next[7]=2;
    i=8,   j=3,  next[8]=3;
    i=9,   j=4,  next[9]=4;
    i=10,  j=5,  next[10]=5;
    i=11,  j=6,  next[11]=6;
    i=12,  j=7,  next[12]=7;
    i=13,  j=8,  next[13]=8;
    i=14,  j=9,  next[14]=9;
    i=15,  j=10, next[15]=10;
          j=next[10] => j=5;
          j=next[5] => j=1;
          j=next[1] => j=0;
    i=16,  j=j+1 => j=1  next[16]=1;
    

    以上是整个next数组的推导过程,这里需要通过i 和j 的变化来理解代码的执行原理。
    第一段:

    i=1,   j=0,  next[1]=0;
    i=2,   j=1,  next[2]=1;
          j=0,  
    i=3,   j=1,  next[3]=1;
          j=0,  
    i=4,   j=1,  next[4]=1; 
          j=0,  
    i=5,   j=1,  next[5]=1; 
          j=0,
    i=6,   j=1,  next[6]=1;
    

    第一句初始赋值,第二句是由于j==0满足了if条件执行了下面的语句,所以next[2]=1;然后又由于T[i]与Tji]与T[j]不相等,j也不为0,所以执行回溯语句,j又变为了0;这样从j=2~j=5 一直是这样重复的。并且最后的next[6]=1也是由于前面j=0,然后通过if判断语句并执行后面的语句产生的。
    第二段:

    i=7,   j=2,  next[7]=2;
    i=8,   j=3,  next[8]=3;
    i=9,   j=4,  next[9]=4;
    i=10,  j=5,  next[10]=5;
    i=11,  j=6,  next[11]=6;
    i=12,  j=7,  next[12]=7;
    i=13,  j=8,  next[13]=8;
    i=14,  j=9,  next[14]=9;
    i=15,  j=10, next[15]=10;
    

    从这里的第一个开始,由于前面T[i]==T[j](T[6]=T[1])成立,所以进入到if判断语句并且执行对应的程序段,结果就依次呈现,从i=7~i=15,一直这样重复;发现:
    (1)i-j 值为5从这里开始一直成立
    (2)这个5正好是“基础串”(abcde)的长度
    第三段:

           j=next[10] => j=5;
           j=next[5] => j=1;
           j=next[1] => j=0;
    i=16,  j=j+1 => j=1  next[16]=1;
    

    由于i=15时,j=10,T[i]与T[j]不相等,j值回溯,先回溯到 j=5,再回溯到 j=1,最后再到 j=0;发现从10~5也是跨过了5个字符的长度。
    所以5也是每次回溯的跨度。相当于每次退回到上一个周期的对应位置时,需要减去周期。
    然后值得注意的一点就是每个举例的串结尾都是xy,x很好理解,而y其实是因为如果结尾是x时,j=x的下标后,不再满足while循环的判断语句,就会跳出循环,那么对于在讨论问题时需要让 j 回溯,所以在最后再加上一个y,会更严谨。
    以上就是我对语句

       j=next[j];
    

    这条语句的 j 值回溯功能的理解。

    因此这个next数组的建造就完成了。下面是将这个next数组真正放在模式匹配算法当中,它如何发挥作用,以及这个算法的原理将在下面讲解:
    首先是代码:

    int Index_KMP(String S,String T,int pos)
    {
     int i=pos;
     int j=1;
     int next[255];
     get_next(T,next);
     while(i<=S[0] && j<=T[0])
     {
      if(j==0||S[i]==T[j])
      {
       i++;
       j++;
      }
      else 
      {
       j=next[j];
      }
     }
     if(j>T[0]) 
     {
      return i-T[0];
     }
     else 
     {
      return 0;
     }
    }
    

    解析:
    ①首先前两句:

     int i=pos;
     int j=1;
    

    (1)将 i 赋值为pos,因为需要查找的是串T在串S中第pos个字符之后的位置。
    (2)T串需要从第一个字符开始匹配。
    ②下面两句就是为T串的next数组个元素赋值。

     int next[255];
     get_next(T,next);
    

    也就是通过前面定义获得的next数组的函数,来得到T串对应的next数组。

    while循环的条件:

    while(i<=S[0] && j<=T[0])
    

    关键:当 i >S的长度时,表示找完S串,发现没有与T串相等的子串;当 j >T串长度时,表示在S串中找到了相等的子串。

    if(j==0||S[i]==T[j])
      {
       i++;
       j++;
      }
    
    j=0:首先需要知道它一定是回溯到这里的,然后执行下面的语句:i++;j++;表示的就是S串中的 i 值加一,也就是位于S串中的子串的首字符位置需要向下移动一个。并且 j 加一,j 就成了1,表示T串也要从第一个字符开始。
    

    else 
      {
       j=next[j];
      }
    

    (1)这里就是 j 值的回溯;关键:与前面所讲的定义next数组的函数时的回溯是一样的道理:它每次退回的位置都是前一个”基础串“中与x在自身所在”基础串“中相同的位置。也就是此时的 j 在T串前面的周期中的位置。根据之前的讲述,多多思考,会更好得到理解这些生硬的语句。
    (2)结合这里并理解上面的 j==0语句:当S[i]!=T[1] 时,就会执行 j=next[1];此时 j 变为了0;就是说T串的第一个字符就与S串的第 i 个字符不相等。就会让S串的 i 加一,移动到下一个字符; j 先回溯到0,再加一,表示重新来到第一个。
    (3)其实从这里,还可以进一步理解执行j=next[j]回溯时,除了先从后往前回到各个周期中的位置之外,最后两次回溯都是j 先到1,再到0这样的原因。带入到上面的匹配算法中就可以发现,j 回溯到1,是为了直接让S[i]与T[1]进行比较,如果两者不相等,那么 i 需要后移,并且 j 需要回溯到0,才能执行到 j++ 从而也能够从第一个字符开始。

     if(j>T[0]) 
    {
     return i-T[0];
    }
    

    此时j 是由于之前的S[I]==T[j]成立,就是前面所说的正确找到对应的串,然后由于它还是要进入到循环中执行i++;j++;所以最后的j 正好比T串的长度大1;所以满足这里的if判断语句,就代表找到了。那么就需要输出该子串在S串中的第pos个字符之后的位置:

     return i-T[0];
    

    其实这里就和之前所讲的普通的模式匹配算法对正确的子串在主串中的位置输出是一样的:因为最后的S[i]与T[j]相等后,一定会再执行一遍 ++i 与 ++j,所以此时的 i 表示的是在S中与T的所有字符中相等的最后一个字符的下一个位置。那么,它再减去T的长度,就可以得到在S中与T相等的子串的第一个元素的下标,也就是要求的子串T在主串S中的第pos个字符之后的位置。

    以上就是一般的KMP模式匹配算法的整个建立,原理和运行过程,还有KMP模式匹配算法的改进,我将在后面的博客中写道。

    展开全文
  • KMP算法是一种改进的字符串匹配算法,KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP...
  • 串模式匹配算法的几种代码实现

    千次阅读 2015-07-31 12:05:40
    c语言中字符处理的库函数还是比较全的,c++里的string类就更不用说了。有些处理函数虽然已封装为库函数,直接调用即可,但是正在学习数据结构,还是想敲些代码,以便总结+巩固。 首先,总结一下常用的c语言中字符...
  • 串模式匹配算法-我的理解

    千次阅读 2007-02-12 22:52:00
    我今天才真正的看懂了,串模式匹配算法KMP,我以前学过但是没有深入的理解。今天我让自己理解了,其实说到底要特别注意KMP算法和其中的NEXT值的求法是一个递推的过程,首先来看看最简单的匹配算法的形式。int index...
  •  以下介绍两种常见的模式匹配算法: Brute-Force模式匹配算法 暴风算法,又称暴力算法。  算法的核心思想如下: 设S为目标,T为模式,且不妨设: S=“s0s1s2…sn-1” , T=“t0t1t2 ...
  • 字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽      §1Boyer-Moore(BM)算法   Boyer-Moore算法原理   Boyer-Moore算法是一种基于后缀匹配的模式串匹配...
  • 字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽     本文内容框架: §1 Boyer-Moore算法 §2 Horspool算法 §3 Sunday算法 §4 KMP算算法 §5 KR算法 §6 AC...
  • 模式匹配算法——KMP

    千次阅读 2013-04-18 17:57:47
    声明 ... 原文的“text”翻译为主,通常用S表示,长度为n; 原文的"pattern"翻译为模式串,通常用T表示,长度为m;...在移动了模式串之后,原始的算法(应该就是普通的BF吧~)忽略了之前匹配的信息,
  • 模式匹配算法 – BF算法详解

    千次阅读 2020-03-19 22:13:01
    算法目的:确定主中所含子串第一次出现的位置,这里的子串也称为模式串。 设计思想: (1)主模式串逐个字符进行比较 (2)当出现字符不匹配(失配)时,主的比较位置重置为起始位置的...
  • 我上一篇文章写的堆存储的就是用的朴素的模式匹配算法。这种算法很简单,就是子串和主进行对应位置的匹配,如果发生失配,那么主和子串都进行回溯,主回溯到开始匹配位置数目加一,子串回溯到零。 代码如下
  • KMP算法 模式匹配算法优秀总结

    千次阅读 2016-05-20 12:21:14
    这几天学习kmp算法,解决字符的匹配问题,开始的时候都是用到BF算法,(BF(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符与模式T的第一个字符进行匹配,若相等,则继续比较S的...
  • KMP模式匹配算法

    千次阅读 2018-11-29 17:14:50
    KMP模式匹配算法 KMP算法可以说是一个很经典的模式匹配算法了,刚开始并没有看懂,多看几遍就好了。 朴素模式匹配算法(KMP算法没提出来之前的常用的匹配算法) 当我们在一篇文章中去搜索一个单词的时候,就是在...
  • -定义和模式匹配算法

    千次阅读 2017-03-12 21:38:59
    5.2 的定义 今天我们就是来研究""这样的数据结构。先来看定义。 ( string )是由零个或多个字符组成的有限序列,又名叫字符 。...ai(1中的字符数目n称为的长度,定义中谈到"有限"是长度n是一个有限的
  • 字符串模式匹配指的是,找出特定的模式串在一个较长的字符串中出现的位置。 朴素的模式匹配算法 很直观的可以写出下面的代码,来找出模式串在一个长字符串中出现的位置。 1: /* 2: 朴素的模式匹配算法 ...
  • 模式匹配算法 子串的定位操作通常称为的 模式匹配,其中T称为 模式。 一般的求子位置的定位函数(Brute Force)我写java的代码是这样的int index(String S,String T,int pos){ char[] s_arr = S....
  • KMP模式匹配算法详解

    万次阅读 2020-02-23 15:48:40
    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主的匹配...
  • 朴素的模式匹配算法 一个例子: 从主 S = "goodjob"中,找到子串 T = "job"的位置。我们通常需要下面的步骤。 1. 将子串"job"与主S从第一位对应匹配。即判断 whether 'g' == 'j'; 2. 判断结果为否,继续匹配 ...
  • 模式匹配算法

    千次阅读 2015-06-08 07:38:39
    简单模式匹配算法 BF算法(Brute-Force,又称古典的、经典的、朴素的、穷举的) 带回溯,速度慢 算法设计思想: 将主S的第pos个字符和模式T的第1个字符比较,若相等,继续逐个比较后续字符;若不等,从主S...
  • (2)--模式匹配算法

    千次阅读 2014-02-14 16:49:33
     当主T(长为m)和子串S(长为n)的比较字符不相等时,主的指针i需要指向之前开始比较的位置的后面一个字符(相应的子串的指针j需要重新到1),,这样依次拿子T和主的一个连续子字符比较知道两个相等为止。...
  • 由于毕业设计(入侵检测)的需要,这两天仔细研究了BM模式匹配算法,稍有心得,特此记下。    首先,先简单说明一下有关BM算法的一些基本概念。    BM算法是一种精确字符匹配算法(区别于模糊匹配...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,966
精华内容 22,786
关键字:

串的模式匹配算法是指