PSJay Blog

#FIXME, seriously

理解 KMP 算法

| Comments

昨天@小树问我还记不记得 KMP 算法,我试着回想之后发现自己已经记不清太多细节,只记得 matrix67 大神有写过这样一篇文章,所以今天特地抽时间又看了看 KMP 算法,顺便记下来。

学过数据结构或者算法课的人应该都清楚 KMP 算法的作用:判断一个字符串(模式串,Pattern)是不是另一个字符串的子串。

大一的新生学过 C 语言之后肯定都会觉得这很容易,并可以写出像下面这样的代码来解决问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 代码 #1, naive solution
**/
void isSubstring(char *text, char* pattern) {
    int i, j;
    for(i = 0; text[i] != '\0'; i++) {
        for(j = 0; text[i + j] != '\0' && pattern[j] != '\0'; j++) {
            if(text[i+j] != pattern[j]) {
                break;
            }
        }

        if(pattern[j] == '\0') {
            printf("yes\n");
            return;
        }
    }
    printf("no\n");
}

这没错,但不够好。假设两个字符串的长度分别为 m 和 n,两层循环导致了这个算法的时间复杂度达到了 O(mn),在字符串长度较长并且运气较差的情况下,这要花费太多的时间。不过这个算法的思想是正确的,我们需要做的只是简化它。

如果有两个字符串 T, P,长度分别为 m 和 n。用 i, j 表示 T[i..i+j] == P[0..j]。

假设 T = “abababaababacb", P = "ababacb"。在上面的例子中,当 i = 0,j = 4 时:

过程 #1:

   0 1 2 3 4 5 
T: a b a b a b ...
P: a b a b a c ...
   0 1 2 3 4 5

发现 T[5] != P[5],所以内循环跳出,将进入下一次外循环,也就是 i = 1 时:

过程 #2:

   0 1 2 3 4 5 
T: a b a b a b ...
P:   a b a b a ...
     0 1 2 3 4

当程序发现 T[i+0] != P[0] 时,这次匹配过程也将失败。但其实这次比较是完全多余的,因为我们在第一次进行匹配的时候已能得知: T[0..4] = “ababa",T[1] = "b” 是不可能和 P[0] = “a” 相等的,这次比较完全可以避免。比较好的办法是在第一轮匹配失败之后,直接让 i = 2,而不是 1,就像这样:

过程 #3:

   0 1 2 3 4 5 6 7
T: a b a b a b a a ...
P:     a b a b a c ...
       0 1 2 3 4 5

KMP 算法正是这样做的。

接下来要定义一些抽象的东西。首先,定义字符串 x 和 y 的重叠(overlap为: x 的后缀和 y 的前缀相等的最大串。例如, x= “lol”, y = “lola",那么, x 和 y 的重叠就是 "l"。注意,x 和 y 的重叠不能等于 x 或 y 本身。

简化外层循环

我们可以借助“重叠”来简化上述算法的外层循环。所谓简化外层循环,其实就是灵活地确定 i 的每次循环的步长,而不是让 i 简单粗暴地在每次循环后自增 1。

值得再次说明,我们已经约定,T[i..i+j] 和 P[0..j] 在是相等的,可以称之为“已匹配字符串”。令 s 为已匹配字符串与 P 的叠加,那么 i 下一次循环的步长就是已匹配字符串的长度减去 s 的长度(注意,为了保证 i 持续增大,步长不能小于 1,如果按上述方法算出来的步长为 0, 则取 1)。这样,就完成了“对齐”工作。 例如,过程 1 中,已匹配字符串为 “ababa",s = "aba",所以 i 的下一次步长为 "ababa” 的长度 - “aba” 的长度 = 2,正如过程 3 所示。我们定义个一个 overlap 函数,它返回两个字符串的叠加的长度。因此,代码 1 可以简化成这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 代码 #2,外层循环简化的算法,注意,这是伪代码
**/
void isSubstring(char *text, char* pattern) {
  int i = 0;
  while(i < m) {
      for(j = 0; text[i + j] != '\0' && pattern[j] != '\0'; j++) {
            if(text[i+j] != pattern[j]) {
                break;
            }
        }

        if(pattern[j] == '\0') {
            printf("yes\n");
            return;
        }

        i = i + max(1, j - overlap(P[0..j - 1], P[0..n - 1]));
  }
  printf("no\n");
}

这样, i 的步长就不是固定不变的 1 了,减少了很多不必要的比较。

简化内层循环

也许你注意到了,内层循环也有可优化的地方。看代码 2 的第 7 行,每次进入内层循环,我们都将 j 赋值为 0,事实上这也是不必要的,只需要从叠加字符串后面开始比较就可以了,因为我们就是按照叠加字符串来“对齐”的。例如,过程 1 的叠加字符串为“aba”,所以在过程 3 中,我们一开始就可以让 T[5] 和 P[3] 比较。因此,代码 2 又能这样进行简化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 代码 3,简化内层循环,依然是能以假乱真的伪代码
*/
void isSubstring(char *text, char* pattern) {
  int i = 0;
  int o = 0;
  while(i < m) {
      for(j = o; text[i + j] != '\0' && pattern[j] != '\0'; j++) {
            if(text[i+j] != pattern[j]) {
                break;
            }
        }

        if(pattern[j] == '\0') {
            printf("yes\n");
            return;
        }

        o = overlap(P[0..j - 1], P[0..n - 1]);
        i = i + max(1, j - o);
  }
  
  printf("no\n");
}

这样,又能在开始内层循环时,减少许多不必要的比较。

这就是 KMP 算法的思想。

overlap 函数

观察一下 overlap 函数的每次调用,它只和 P 和 j 有关!也就是说,这个函数只跟模式串有关系,所以,我们可以用一个预处理函数算出不同 j 值对应的 overlap 的值,需要的时候直接查找就可以了(动态规划的思想)。

我们对 x 和 y 的重叠的定义为:最长的,既是 x 的后缀,又是 y 的前缀的字符串。如果去掉“最长的”这个条件,我们称它为“短重叠”。例如,"ababa" 和 “ababac” 的重叠是 “aba",短重叠是 "a"。有一个很容易得出的结论:字符串 x 和 y 的短重叠一定是它们的重叠的后缀。这也很容易证明:若 a 是 x 和 y 的重叠, b 是 x 和 y 的短重叠,根据定义,有: a 和 b 都是 x 的后缀, y 的前缀。既然 a 和 b 都是 x 的后缀,并且 b 的长度小于 a 的长度,那么 b 就是 a 的后缀。因此,我们可以用这种方法列出 x 和 y 的重叠和所有的短重叠(从长至短):

1
2
3
4
5
6
7
/**
* 代码 4 , 列出 x, y 的重叠和短重叠,依然是伪代码
*/
while(x != null) {
  x = overlay(x, y);
  output x;
}

前面已经说过,我们可以写一个预处理函数将需要用到的数据(j 等于各个值时, P[0..j - 1] 和 P 的重叠的长度)储存起来。假设我们将这个结果储存在 next 数组里, next[n] 表示 P[0..n - 1] 和 P 的重叠的长度。

接下来考察 P[0..j - 1] 和 P 的重叠的长度的一般情况(n >= j > 0)。

设 P[0..j - 1] 与 P 的重叠为 w,短重叠为 w', w'‘, w’‘’…。 我们依次令 z = w', w'‘, w’‘’ ,那么,第一个能满足 P[z.length] = P[0..j] 的叠加(或短叠加),后面加上 P[j],就是 P[0..j] 和 P 的叠加。

因此,我们可以根据这个结论,写下这样的 overlay 函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 代码 5, overlay 函数
*/
int* overlap(char* pattern) {
  next[0] = -1;
  for(int i = 0; pattern[i] != '\0'; i++) {
      next[i + 1] = next[i] + 1;
      while (next[i + 1] > 0
              && pattern[i] != pattern[next[i + 1] - 1]) {
                          
          next[i + 1] = next[next[i + 1] - 1] + 1;
      
      }

  }
  return next;
}

通常,国内的教材喜欢把这个函数叫做 next 函数。

因此, KMP 算法的一个 C 语言实现如下:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include "stdio.h"
#include "malloc.h"
#include "string.h"

/****************************
*   A implementation of KMP algorithm
*   @author PSJay
****************************/
/**
*   return the bigger one of 2 integers
**/
int max(int a, int b) {
    return a > b? a:b;
}

/**
*   initialize next array with pattern
**/
void overlap(char *pattern, int *next) {
    next[0] = -1;
    int i;
  for(i = 0; pattern[i] != '\0'; i++) {
      next[i + 1] = next[i] + 1;
      while (next[i + 1] > 0
              && pattern[i] != pattern[next[i + 1] - 1]) {

          next[i + 1] = next[next[i + 1] - 1] + 1;

      }

  }
}


/**
*   is pattern a substring of text?
*/
void isSubstring(char *text, char *pattern) {
    int i = 0;
  int o = 0;

  int *next = malloc(sizeof(int) * (strlen(pattern) + 1));    // create next array
    overlap(pattern, next); // use overlap function to init next array

    int j;
  while(i < strlen(text)) {
      for(j = o; text[i + j] != '\0' && pattern[j] != '\0'; j++) {
            if(text[i+j] != pattern[j]) {
                break;
            }
        }

        if(pattern[j] == '\0') {
            printf("yes\n");
            return;
        }

        o = next[j + 1];
        i = i + max(1, j - o);
  }

  printf("no\n");
}


/**
*   program entry
*/
int main() {
    char *a = "abababaababacb";
    char *b = "ababacb";

    isSubstring(a, b);

    return 0;
}

参考资料: [1] http://www.ics.uci.edu/~eppstein/161/960227.html [2] http://www.matrix67.com/blog/archives/115

Comments