KMP算法

Posted in 2010-01-24 2:27 PMJulius ChenNo Comments »

KMP算法是字符串匹配的一种改进算法，在1977年由D. E. Knuth，J. H. Morris和V. R. Pratt一起提出，并以他们名字的首字母命名。和朴素的模式匹配算法相比，KMP算法最大的特点就是主串指针不回溯。它利用已经得到的“部分匹配”信息来减少不必要的比较而加快字符串的匹配速度。

KMP算法的本质

KMP算法本质上是实现了对自动机的模拟。它通过构造一个有限自动机来搜寻某给定的模式在正文中出现的位置。整个算法的核心就是对自动机的构建（或前缀函数的构建，KMP算法不用计算变迁函数，而是根据模式预先计算出一个辅助函数next来实现更快速的状态切换），当完成有限自动机的构建之后对主串的搜寻就显得很简单了。

前缀函数next的构建

模式的前缀函数包含有模式与其自身的位移进行匹配的信息。这些信息可用于避免在朴素的模式匹配算法中对无用位移的测试。比如主串和模式串在主串指针为Ti、模式串指针为Pj处匹配失败时，可以主串指针不回溯并直接取next函数的值next[j] = k将模式串向右滑动到第k个字符处重新开始比较，而不用去做无用位移的测试。只是这样的操作能成立k必须要满足一定的条件，如下所示：

首先，如果模式串能直接向右滑动到第k个字符处重新开始比较则说明模式串中的前k-1个字符必然已经和主串匹配了，也即必然已经有下面式子，且为了能最大化的向右移动则不能存在更大的k’满足下面式子：

<1>： P1 P2 … Pk-1 = Ti-k+1 Ti-k+2 … Ti-1

而由已经比较所得的“部分匹配”信息可知：

<2>： Pj-k+1 Pj-k+2 … Pj-1 = Ti-k+1 Ti-k+2 … Ti-1

因此由式子<1>和式子<2>我们可以推得：

<3>： P1 P2 … Pk-1 = Pj-k+1 Pj-k+2 … Pj-1

也就是k必须要满足式子<3>的条件！由这个式子也可以看出k就是模式中第j个字符所拥有的最长真后缀同时是模式前缀的串的长度，且k的取值和主串T无关！

那有了式子<3>之后如何去求模式的每个字符所对应的k(next[j])的值呢？

由上面结论可知，当j = 0时next[j] = -1，因为第一个字符没有真后缀同时是模式的前缀。其他情况时，next[j]则可以由它前一个位置字符的next值推出。

比如我们要求next[j+1]，假设已有next[j] = k，即已有P1 P2 … Pk-1 = Pj-k+1 Pj-k+2 … Pj-1。如果此时有Pj = Pk，则表明P1 P2 … Pk = Pj-k+1 Pj-k+2 … Pj，所以next[j+1] = next[j] + 1 = k + 1。如果Pj ≠ Pk，则此时可把求next函数值的问题又看成是一个模式匹配的问题，整个模式串既是主串又是模式串。所以我们再从next[k]处开始重新进行比较，若Pj = Pnext[k]，则next[j+1] = next[next[k]] + 1。否则，再从next[next[k]]开始重新比较 … 这样一直下去，直到Pj和模式中某个字符匹配成功或next[...] = -1，则next[j+1] = 0。如例子1：

例子1：
                0 1 2 3 4 5 6 7
模式:        a b a a b c a c
next[j]      -1 0 0 1 1 2 ? ?

当求next[6]时，由于P5 ≠ P2（Pnext[5]），所以接着去比较P5和P0（Pnext[next[5]]），可P0已经等于-1，说明已经到头了，所以next[6] = 0。同理，next[7] = 1。

前缀函数的C/C++代码实现如下：

  1. void prefix_function(char *p, int *next)
  2. {
  3.     int j, k;
  4.     next[0] = -1;
  5.     j = 0; k = -1;
  6.     int length = strlen(p) - 1; // next[0] 已不用计算
  7.     while (j < length) {
  8.         if (k == -1 || p[j] == p[k]) {
  9.             next[j+1] = k + 1;
  10.             k++;
  11.             j++;
  12.         }
  13.         else {
  14.             k = next[k];
  15.         }
  16.     }
  17. }

KMP算法的实现

当next函数求出来之后，再在主串上搜寻模式串就相对简单了，整个过程和朴素的模式匹配算法差不多，C/C++代码实现如下：

  1. int kmp_matching(char *t, char *p)
  2. {
  3.     int t_len = strlen(t);
  4.     int p_len = strlen(p);
  5.  
  6.     // 先预先求出next函数
  7.     int *next = new int[t_len];
  8.     prefix_function(p, next);
  9.  
  10.     int i, j;
  11.     i = 0; j = 0;
  12.     while (i < t_len && j < p_len) {
  13.         if (j == -1 || t[i] == p[j]) {
  14.             i++;
  15.             j++;
  16.         }
  17.         else {
  18.             j = next[j];
  19.         }
  20.     }
  21.  
  22.     if (next != NULL) {
  23.         delete[] next;
  24.         next  = NULL;
  25.     }
  26.  
  27.     if (j == p_len)
  28.         return i - p_len;
  29.  
  30.     return -1;
  31. }

时间复杂度分析

由于KMP算法构造了一个自动机来匹配模式串，因此其主串中的每个字符只需比较一次，并且每个字符比较的时间为常数，所以其时间复杂度为线性。m长度的主串比较时间为O(m)。而前缀函数由于是提前构建，用平摊分析方法可知n长度的模式花费的时间为O(n)，所以KMP算法总的时间复杂度为O(m+n)。

补充说明

关于next函数（前缀函数）的求法，严版《数据结构》中提到一点，即上面所给的代码还可以改善。举个例子，比如说模式P为aaaab，主串T为aaabaaaab时，用上面的算法得出next[] = {-1, 0, 1, 2, 3}。因为P3 = a和T3 = b不匹配，所以接下来还需要拿P2P1P0去和T3去比较，可这些比较不是必需的，因为P2 = P1 = P0 = P3，既然P3比较不成功，他们比较怎么又会成功呢？所以这时候就可以优化。当计算next函数时，如果比较失败的字符和他的next[]所对应的字符不等，则其next[]依旧按上面方法计算，否则其next[]等于其next[]所对应的字符的next值。反映到算法上如下：

  1. void prefix_function(char *p, int *next)
  2. {
  3.     int j, k;
  4.     next[0] = -1;
  5.     j = 0;
  6.     k = -1;
  7.     int length = strlen(p) - 1; // next[0] 已不用计算
  8.     while (j < length) {
  9.         if (k == -1 || p[j] == p[k]) {
  10.             if (p[j+1] != p[k+1])
  11.                 next[j+1] = k + 1;
  12.             else
  13.                 next[j+1] = next[k+1];
  14.             j++;
  15.             k++;
  16.         }
  17.         else {
  18.             k = next[k];
  19.         }
  20.     }
  21. }
Strings, , , ,

文章若无注明则属原创，转载请以链接形式注明出处。
本文地址：http://www.juliuschen.com/archives/21.html

Leave a Reply