KMP串匹配算法

时间:2021-07-14 07:34:57

最近趁项目空闲时间,多补补数据结构及算法的知识,阅读严蔚敏的《数据结构》一书中提到KMP串匹配算法,不是特别理解,特别求next数组的算法。于是上网查了下资料,发现很多网友写了很多不错的文章,对于理解很有帮助。

1、http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html

2、http://www.cnblogs.com/hi5000/archive/2012/05/28/2520915.html

3、http://www.cnblogs.com/wentfar/archive/2011/12/17/2291340.html

写技术博客对于搞IT的人来说是个不错的习惯,于是我也把自己学习到的一点东西记录下来,由于偷懒,有些文字上的东西就直接引用以上链接中的内容了~

                                                                              在介绍KMP算法之前,先介绍一下BF算法。

一.BF算法

    BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。

    举例说明:

    S:  ababcababa

    P:  ababa

 BF算法匹配的步骤如下

            i=0                                   i=1                                 i=2                               i=3                              i=4

  第一趟:ababcababa         第二趟:ababcababa      第三趟:ababcababa    第四趟:ababcababa    第五趟:ababcababa

            ababa                             ababa                          ababa                        ababa                       ababa

            j=0                                    j=1                                 j=2                              j=3                              j=4(i和j回溯)

 

              i=1                                   i=2                                  i=3                                i=4                         i=3

 第六趟:ababcababa         第七趟:ababcababa       第八趟:ababcababa     第九趟:ababcababa   第十趟:ababcababa

             ababa                               ababa                           ababa                        ababa                         ababa

             j=0                                    j=0                                  j=1                               j=2(i和j回溯)            j=0

 

                      i=4                                    i=5                                 i=6                                 i=7                                 i=8

第十一趟:ababcababa       第十二趟:ababcababa    第十三趟:ababcababa   第十四趟:ababcababa   第十五趟:ababcababa

                     ababa                               ababa                           ababa                          ababa                          ababa

                     j=0                                    j=0                                  j=1                                 j=2                                j=3

 

                               i=9

第十六趟:ababcababa

                      ababa

                               j=4(匹配成功)

 其实在上面的匹配过程中,有很多比较是多余的。在第五趟匹配失败的时候,在第六趟,i可以保持不变,j值为2。因为在前面匹配的过程中,对于串S,已知s0s1s2s3=p0p1p2p3,又因为p0!=p1!,所以第六趟的匹配是多余的。又由于p0==p2,p1==p3,所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。

实现代码如下:

 1 //常规方法匹配
 2 int BF_index(const char *p1, const char *p2)
 3 {
 4     unsigned int i= 0 ,j = 0;
 5     int len1 = strlen(p1);
 6     int len2 = strlen(p2);
 7 
 8     while(i<len1 && j<len2)
 9     {
10         if(p1[i] == p2[j])
11         {
12             ++i;
13             ++j;
14         }
15         else
16         {
17             i = i-j+1;  //指针回溯,主串指针退回到原位置的下一个位置开始匹配
18             j = 0;
19         }
20     }
21     return (j == len2) ? (i-len2+1) : 0;
22 }

1、我发现许多书或者网上的代码,在while循环里面利用strlen求字符串的长度,结果每执行次while循环就执行次strlen函数,这其实是件效率很低的事情,可以把strlen函数放在循环外求解,这样就只执行一次strlen函数,

    因此,不好的编程习惯会让程序效率降低很多,而且可能引起许多不可预料的事情。

二.KMP算法

    KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。

在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。

对于next[]数组的定义如下:

1)next[j]=-1,j=0

2)next[j]=max k:0<k<j P[0...k-1]=P[j-k,j-1]

3)next[j]=0 ,其他

如:

P      a    b   a    b   a

j       0   1    2   3   4

next -1  0    0   1   2

即next[j]=k>0时,表示P[0...k-1]=P[j-k,j-1]

因此KMP算法的思想就是:在匹配过程称,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。

KMP匹配代码实现如下:

 1 /***
 2 *    主要功能:KMP匹配
 3 *    @param const char *p1    主串
 4 *    @param const char *p2    模式串
 5 *    @param int         pos   匹配起始位置
 6 *    @param const int  *next  模式串next数组
 7 *    return int               在主串中匹配的位置
 8 */
 9 int KMP_index(const char *p1, const char *p2, int pos, const int *next)
10 {
11     int i = pos-1;
12     int j = 0;
13     int len1 = strlen(p1);
14     int len2 = strlen(p2);
15 
16     assert((pos-1)>=0 && (pos-1)< len1);
17 
18     while(i<len1 && j<len2)     //i是主串游标,j是模式串游标
19     {
20         if(j == -1                //模式串游标已经回退到第一个位置
21             || p1[i] == p2[j])    //当前字符匹配成功
22         {
23             ++i;                  //满足两种情况时两个游标都要向前进一步
24             ++j;
25         }
26         else
27         {
28             j = next[j];         //匹配不成功,模式串游标回退到当前字符的next值,相当于模式串向右移
29         }
30     } 
31     if(j >= len2)                //匹配成功
32         return i-len2+1;   
33     else 
34         return -1;
35 }

 

求取next[j]

根据next[j]的定义可知,此函数的值取决于模式串的本身以及模式串的失配位置。此时把求解next[j]问题看成是一个模式串自匹配问题即主串和模式串都是P,从主串Pp1开始与模式串Pp0开始进行匹配

当j=0时,由定义得:next[0]=-1;

当j!=0时,我们思路是:按照主串的下标j由小及大,依次求next[1]、next[2]、...、next[m-1],m为模式串的维数。现在假设已知next[j]=k,且next[t](t<j)均已求得。如果求得next[j+1]与next[j]的关系,那么所有的next函数值均可被求出。

此时,由next[j]的定义可知:'pj-kpj-k+1...pj-1'='p0p1...pk-1',且k为最大值,下面分两种情况讨论:

(a) 如果pj=pk,结合'pj-kpj-k+1...pj-1'='p0p1...pk-1'可以得到'pj-kpj-k+1...pj-1pj'='p0p1...pk-1pk',又不存在k'>k满足该式,由next函数的定义可知:next[j+1]=k+1,也即:next[j+1]=next[j]+1。这个式子的意味着,该情况下主串字符指针(j+1)位置处的next[j+1]可以由当前j位置处的next[j]1求得。(由于下标最小的next函数值next[1]=0是已知的,这使得按下标由小及大的顺序求解所有next函数值成为可能,这种情况对应着下面伪代码的 if(P[i] == P[j])语句部分)

 

(b) 如果pj!=pk,将模式串向右滑动至k'(k'=next[k]<k<j)位置,使得主串的pj字符与模式串的pk'字符比较。

①如果此时pj=pk'(k'<k),结合'pj-kpj-k+1...pj-1'='p0p1...pk-1',则有'pj-k'pj-k'+1...pj-1pj'='p0p1...pk'-1pk'',由next函数的定义该式等价于:next[j+1]=k'+1=next[k]+1(观察下标k<j,由于next[t](t<=j)均为已知,则一定可以求出next[j+1])。

②如果此时pj!=pk',则将模式串继续向右滑动,直至pj和模式串的某个字符pk_lucky匹配成功,此时pj=pk_lucky(k_lucky<k),结合'pj-kpj-k+1...pj-1'='p0p1...pk-1',则有'pj-k_luckypj-k_lucky+1...pj'='p0p1...pk_lucky',由next函数的定义该式等价于:next[j+1]=k_lucky+1=next[...next[k]...]+1(在几次连续的滑动过程中,每次迭代k'=next[k],k'<k<j恒成立,由于next[t](t<=j)可知已知,则一定可以求出next[j+1])。

①和②的讨论说明,无论经过多少次滑动,只要主串的pj最终与模式串pk_lucky字符匹配成功,则主串字符指针(j+1)位置处的next[j+1]一定可以由next[t](其中t<=j)1求得(这种情况对应着下面伪代码的else语句部分)

③尽管向右滑动,一直到j=next[t]=-1,很不幸找不到k'使得pj=pk',这相当于匹配过程中无解,此时由定义知next[j+1]=0(这种情况对应着下面伪代码的if(j==-1)部分)

 

故伪代码如下:

void get_next(SString P,  int next[]){

    //求模式串P的next函数值并存入数组next中,i、j分别代表主串、模式串的下标

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

    while(i < len(P)-1){

        if( j==-1 || P[i] == P[j] ) { ++i; ++j; next[i] = j; }//每当自增i和j,得到一个新的next[i]

        else j = next[j];//模式串向右移动

    }

}

实现代码如下:

 1 //求模式串的next
 2 void getnext(const char *p, int *next)
 3 {
 4     int j = 0, k=-1;
 5     next[0] = -1;
 6     int len = strlen(p);
 7 
 8     while(j < len)
 9     {
10         if(k == -1                // 如果模式串游标已经回退到第一个字符
11             || p[j] == p[k] )     //如果匹配成功, p[j]==p[k] 
12         {
13             ++j;
14             ++k;
15             next[j] = k;          //存放当前的next值为此时模式串的游标值
16         }
17         else
18             k = next[k];          //p[j]!=p[k],匹配不成功j就回退到上一个next值
19     }
20 }

 

完整的测试代码如下:

KMP串匹配算法KMP串匹配算法View Code
  1 /***************************************************
  2 *
  3 *   参考资料:《数据结构--严蔚敏版》
  4 *
  5 ****************************************************/
  6 
  7 #include <stdio.h>
  8 #include <string>
  9 #include <assert.h>
 10 
 11 //常规方法匹配
 12 int BF_index(const char *p1, const char *p2)
 13 {
 14     unsigned int i= 0 ,j = 0;
 15     int len1 = strlen(p1);
 16     int len2 = strlen(p2);
 17 
 18     while(i<len1 && j<len2)
 19     {
 20         if(p1[i] == p2[j])
 21         {
 22             ++i;
 23             ++j;
 24         }
 25         else
 26         {
 27             i = i-j+1;  //指针回溯,主串指针退回到原位置的下一个位置开始匹配
 28             j = 0;
 29         }
 30     }
 31     return (j == len2) ? (i-len2+1) : 0;
 32 }
 33 
 34 //求模式串的next
 35 void getnext(const char *p, int *next)
 36 {
 37     int j = 0, k=-1;
 38     next[0] = -1;
 39     int len = strlen(p);
 40 
 41     while(j < len)
 42     {
 43         if(k == -1                // 如果模式串游标已经回退到第一个字符
 44             || p[j] == p[k] )     //如果匹配成功, p[j]==p[k] 
 45         {
 46             ++j;
 47             ++k;
 48             next[j] = k;          //存放当前的next值为此时模式串的游标值
 49         }
 50         else
 51             k = next[k];          //p[j]!=p[k],匹配不成功j就回退到上一个next值
 52     }
 53 }
 54 
 55 /***
 56 *    主要功能:KMP匹配
 57 *    @param const char *p1    主串
 58 *    @param const char *p2    模式串
 59 *    @param int         pos   匹配起始位置
 60 *    @param const int  *next  模式串next数组
 61 *    return int               在主串中匹配的位置
 62 */
 63 int KMP_index(const char *p1, const char *p2, int pos, const int *next)
 64 {
 65     int i = pos-1;
 66     int j = 0;
 67     int len1 = strlen(p1);
 68     int len2 = strlen(p2);
 69 
 70     assert((pos-1)>=0 && (pos-1)< len1);
 71 
 72     while(i<len1 && j<len2)     //i是主串游标,j是模式串游标
 73     {
 74         if(j == -1                //模式串游标已经回退到第一个位置
 75             || p1[i] == p2[j])    //当前字符匹配成功
 76         {
 77             ++i;                  //满足两种情况时两个游标都要向前进一步
 78             ++j;
 79         }
 80         else
 81         {
 82             j = next[j];         //匹配不成功,模式串游标回退到当前字符的next值,相当于模式串向右移
 83         }
 84     } 
 85     if(j >= len2)                //匹配成功
 86         return i-len2+1;   
 87     else 
 88         return -1;
 89 }
 90 
 91 int main(int argc, char* argv[])
 92 {
 93     const char *p1 = "aabcabcaabacabaa";
 94     const char *p2 = "abac";
 95 
 96     int next[10] = {0};
 97 
 98     //================BF匹配=================
 99     int pos1 = 0;
100     pos1 = BF_index(p1,p2);
101     printf("BF index = %d \n",pos1);
102 
103     //===============KMP匹配================
104     int pos2 = 0;
105     getnext(p2, next);
106     pos2 = KMP_index(p1, p2, 1, next);
107     printf("KMP index = %d \n",pos2);
108 
109     system("pause");
110     return 0;
111 }