字符串的模式匹配(朴素匹配、KMP)

时间:2022-03-03 06:12:41

问题: 用给定的模式P,在目标字符串T中搜索与模式P全同的一个子串,并求出T中的第一个和p全同匹配的子串


方法一朴素模式匹配

(穷举法),目标长度为n,模式长度m时,O(nm)


方法二:KMP

由于朴素模式匹配中存在很多冗余的计算,除掉这些冗余可以加速整个匹配时间,于是有了KMP算法。

例如: abcabefab  与 abe进行匹配,朴素在计算完abc与abe不匹配后,会继续计算b与a是否匹配,c与a是否匹配。

而KMP算法,是尽量找到出现不匹配点时,下一个应该开始计算的位置。如上例abc与abe不匹配后,可以直接计算c是否与a匹配。

KMP算法发现每次出现误配时,应该如何选择下一个要测试的点只跟模式P本身有关。

KMP算法计算字符串特征向量N:构造方法:

定义:模板P的前缀子串(P0 P1 ... P t-1)左子串 (Pi-t ... Pi-2 Pi-1)

字符串的模式匹配(朴素匹配、KMP)

计算模板p第j个位置的特征数ni:最长的 t 能够与前缀子串匹配的左子串 ,计算方式如下:

1.n0 = 0,对于i >1的ni ,假定已知前一位置的特征数ni-1 ,并且ni-1 = k ;
2.如果qi = qk ,则ni = k+1 ;
3.当qi ≠ qk 且 k≠0时,则 令k = n (k -1) ; 让 3. 循环直到条件不满足;
4.当qi ≠ qk 且 k = 0时,则 ni = 0;

例如    a  b  c  a  a  b  a  b  c

next[]  -1  0 0 -1  1  0  2  0  0 

计算特征向量N的算法实现如下

int*Next(String P) {            // 计算向量N

     int m = P.size;               //  m为模板P的长度

     assert( m > 0);              //  若m=0,退出

     int *N = new int[m];      // 动态存储区开辟整数数组

     assert( N != 0);              // 若开辟存储区域失败,退出

     N[0] = -1;

  int i = 0;

  int j = -1;

  while (i < m) {

  while (j >= 0 && P.str[i] != P.str[j]) 

  j = N[j]; 

  i++;

  j++;

  N[i] = j;

  }

      returnN;

}

KMP模式匹配算法实现:

int KMP_FindPat(StringS, String P, int *N, int startindex) {

    // 假定事先已经计算出P的特征数组N,作为输入参数

    int LastIndex = S.size - P.size;       // S末尾再倒数一个模板长度位置

    if ((LastIndex - startindex) < 0)

        return (-1);                               // startindex过大,匹配无法成功

    int i;                                             //i 是指向S内部字符的游标

    int j = 0;                                       // j 是指向P内部字符的游标

   

    for (i = startindex; i < S.size; i++) {          // S游标i循环加1

         //若当前位置的字符不同,则用N循环求当前的j,用于将P的恰当位置与S的i位置对准

         while (P.str[j] != S.str[i] &&  j > 0)     

                     j =N[j];

          if (P.str[j] == S.str[i])              // P[j]与S[i]相同,继续下一步循环

                j++;     

          if ( j == P.size)                         // 匹配成功,返回该S子串的开始位置

                return (i - j +1);

    };

    return (-1);                                  // P和S整个匹配失败,函数返回值为负

}

KMP算法效率分析

循环体中”j = N[j];” 语句的执行次数不能超过n 次。否则, 由于“j = N[]; ”每执行一次必然使得j减少(至少减1),而使得 j 增加的操作只有“j++ ,整个循环中j只加了n次。那么,如果“j = N[j]; ”的执行次数超过n次,最终的结果必然使得j 为负数。这是不可能的。同理可以分析出求N数组的时间为O(m),故,KMP算法的时间为O(n+m)