KMP算法–字符串匹配算法

字符串匹配是我们经常遇到的问题，就是在原字符串中查找子串在原字符串中首次出现的位置。

1. Brute force.

首先我们能想到的，也是最传统的做法就是暴力搜索。

利用计数指针i和j指示主串S和模式串T中当前正待比较的字符位置，从主串S的第pos个字符起和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较。直到模式T中的每个字符依次和主串S中的一个连续字符序列相等，则匹配成功，否则匹配失败。

匹配时间复杂度O(N*M)。

该算法的效率很低，比如说：

主串：ababcabcacbab

子串：abcac

 

image

 

我们看上面的匹配过程在第三趟的匹配中，当i=6、j=4字符比较不相等时，又要从i=3，j=1重新开始比较。但是我们仔细观察可以发现，在i=3和j=1，i=4和j=1以及i=5和j=1这3次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中第4、5和6个字符必然是b、c和a（即模式串中第2、3和4个字符）。因为模式中的第一个字符是a，因此它无需再和这3个字符进行比较，而仅需将模式向右移动3个字符的位置继续进行i=6、j=1时的字符比较即可。

所以就有了KMP算法。

 

2. KMP算法

KMP算法解决的问题是字符匹配，是由Knuth–Morris–Pratt共同开发出来的，这个算法把字符匹配的时间复杂度缩小到O（m+n）,而空间复杂度也只有O(m),n是target的长度，m是pattern的长度。

相比蛮力算法，KMP 算法预先计算出了一个哈希表，用来指导在匹配过程中匹配失败后尝试下次匹配的起始位置，以此避免重复的读入和匹配过程。这个哈希表被叫做“部分匹配值表(Particial match table)”，它的设计是算法精妙之处。

 

部分匹配值表

要理解部分匹配值表，就得先了解字符串的前缀(prefix)和后缀(postfix)。

  • 前缀:除字符串最后一个字符以外的所有头部串的组合。
  • 后缀：除字符串第一个字符以外的所有尾部串的组合。
  • 部分匹配值：一个字符串的前缀和后缀中最长共有元素的长度。

 

举例说明：字符串ABCAB

  • 前缀：{A， AB， ABC， ABCA}
  • 后缀：{BCAB， CAB， AB， B}
  • 部分匹配值：2 （AB）

 

而所谓的部分匹配值表，则为模式串的所有前缀以及其本身的部分匹配值。

举例如下：还是针对字符串ABCAB，它的部分匹配值表为：

A B C A B

0 0 0 1 2

这代表着：字符串ABCAB 中，子串ABC的部分匹配值为 0，而子串ABCA的部分匹配值为 1，诸如此理。

 

我们来看看next函数的定义：

  1. ①：next[j]=0                  当j=1时
  2. ②：next[j] = Max{k|1<k<j,且’p1….pk-1’==pj-k+1…pj-1′}         当此集合不空时
  3. ③：next[j]=1                 其它情况

 

第一种和第三种情况就不用说了，我们来看看第二种：

10fb1396058365

其实我们需要的是找出最大的K值。在满足p1….pk-1 == pj-k+1…pj-1的前提下。

简单的来说：就是求出一个字符串的前缀和后缀中最长共有元素的长度。

 

我们来看代码：

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void getNext(SString T, int next[ ])
{
  //求模式串T的next函数值并存入数组next。
  i = 1;
  next[1] = 0;
  j = 0;
  while(i < T[0]){      //T[0]为T的长度
    if(j == 0 || T[i] == T[j])
    {
      ++i;
      ++j;
      next[i] = j;
    }
    else j = next[j];
  }
}

 

但是，前面定义的next函数在某些情况下还是有缺陷。例如模式 aaaab 在和主串 aabaaaab匹配时，当i=4、j=4时s.ch[4] != t.ch[4],由next[j]的指示还需进行i=4、j=3,i=4、j=2,i=4、j=1这3次比较。实际上，因为模式中第1、2、3个字符和第4个字符都相等，因此不需要再和主串中第4个字符想比较，直接进行i=5、j=1时的字符比较。这就是说，若按上述定义得到next[j] = k，而模式中Pj = Pk，则当主串中字符Si和Pj比较不等时，不需要再和Pk进行比较，而直接和Pnext[k]进行比较，换句话说，此时的next[j]应和next[k]相同。

j                        1   2   3   4   5

模式                 a   a   a   a   b

next[j]             0   1   2   3   4

nextval[j]       0   0   0   0   4

 

next函数的修正算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void getNextVal(SString T, int nextval[ ])
{
  //求模式串T的next函数值并存入数组next。
  i = 1;
  next[1] = 0;
  j = 0;
  while(i < T[0]){
    if(j == 0 || T[i] == T[j])
    {
      ++i;
      ++j;
      if(T[i] != T[j])    next[i] = j;
      else  nextval[i] = nextval[j];
    }
    else j = next[j];
  }
}

 

求出了next数组了，KMP算法也就不在话下了。

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//int kmp_seach(char const*, int, char const*, int, int const*, int pos)  KMP模式匹配函数    
//输入：src, slen主串    
//输入：patn, plen模式串    
//输入：nextval KMP算法中的next函数值数组    
int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)    
{    
    int i = pos;    
    int j = 0;    
    while ( i < slen && j < plen )    
    {    
        if( j == 0 || src[i] == patn[j] )    
        {    
            ++i;    
            ++j;    
        }    
        else    
        {    
            j = nextval[j];              
        }    
    }    
    if( j >= plen )    
        return i-plen;    
    else    
        return -1;    
}

本文链接：http://www.alonemonkey.com/knuth-morris-pratt-algorithm.html