KMP(Knuth-Morris-Pratt)算法

KMP算法是著名并且高效的字符串匹配算法，该算法因Knuth，Morris与Pratt三人联合发表而得名。

问题

给定两个字符串S(n个字符)和W(m个字符)，求W在S中第一次出现的位置。

BF(Brute Force)算法

BF算法是普通的模式匹配的算法，该算法的思想是首先比较S和W的第一个字符，若匹配，则继续比较下一个字符，若不匹配，则从S的第二个字符和W的第一个字符开始，重复上述过程，直到S和W匹配。

该算法的时间复杂度为 O(m*n)

KMP(Knuth-Morris-Pratt)算法

算法思想

在BF算法中，如果发生字符串失配，那么我们会从S的下一个字符开始重头开始匹配，而实际上，在发生失配时，W自身已经包含了足够的信息，以确定下一个匹配的位置，这就是KMP算法的核心思路。

算法实例

不妨设字符串S为 ABC ABCDAB ABCDABCDABDE，W为 ABCDABD。

首先我们从W和S的开头开始匹配，但是我们发现，S[3] = ‘ ‘而W[3] = ‘D’，发生了失配，但我们同时也发现，S[1]到S[3]不与W[0]——也就是’A’相匹配，因此下一次匹配我们直接从S[4]开始，与W[0]进行匹配。

1
2
3
4

      |
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
      |

1
2
3
4

       |
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
       |

随后，我们发现S[10] = ‘ ‘与W[6] = ‘D’失配，注意到W[0]-W[1]与W[4]-W[5]均为”AB”，因此下一次匹配时，我们也不必直接从下一位开始匹配，而是可以从已匹配的尾部的”AB”处继续匹配。

1
2
3
4

             |
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
             |

1
2
3
4

             |
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
             |

下图所示的情况与上述的情况类似，我们直接从尾部的”AB”处继续匹配。

1
2
3
4

                    |
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
                    |

1
2
3
4

                    |
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
                    |

最终找出了完全匹配的位置。

1
2
3
4

                        |
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
                        |

部分匹配表（失配函数）

部分匹配表中的部分匹配值指出了在发生失配时，可以跳过的无效字符数。

我们首先需要了解两个概念：“前缀”和“后缀”。

“前缀”指除了最后一个字符之外，一个字符串的全部头部组合；“后缀”指除了第一个字符之外，一个字符串的全部尾部组合。

部分匹配值就是“前缀”和“后缀”的最长的共有元素的长度。

部分匹配值的实质是，有时候，字符串的头部和尾部会有重复。这样，不能直接将字符串向后移动“字符串长度”位，而是应该移动“字符串长度-部分匹配值”位。

部分匹配表实例

以”ABCDABD”为例——

• “A”的前缀和后缀都为{}，共有元素长度为0；
• “AB”的前缀为{“A”}，后缀为{“B”}，共有元素长度为0；
• “ABC”的前缀为{“A”, “AB”}，后缀为{“C”, “BC”}，共有元素长度为0；
• “ABCD”的前缀为{“A”, “AB”, “ABC”}，后缀为{“D”, “CD”, “BCD”}，共有元素长度为0；
• “ABCDA”的前缀为{“A”, “AB”, “ABC”, “ABCD”}，后缀为{“A”, “DA”, “CDA”, “BCDA”}，共有元素为{“A”}，长度为1；
• “ABCDAB”的前缀为{“A”, “AB”, “ABC”, “ABCD”, “ABCDA”}，后缀为{“B”, “AB”, “DAB”, “CDAB”, “BCDAB”}，共有元素为{“AB”}，长度为2；
• “ABCDABD”的前缀为{“A”, “AB”, “ABC”, “ABCD”, “ABCDA”, “ABCDAB”}，后缀为{“D”, “BD”, “ABD”, “DABD”, “CDABD”, “BCDABD”}，共有元素长度为0；

算法实现（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

int kmp (const char * s, const char * w) {
    int s_idx = 0;
    int w_idx = 0;
    int s_len = strlen(s);
    int w_len = strlen(w);
    int next[w_len];
    generate_next(w, next);
    while (s_idx < s_len && w_idx < w_len) {
        if (w_idx == -1 || s[s_idx] == w[w_idx]) {
            s_idx++;
            w_idx++;
        } else {
             w_idx = next[w_idx];
        }
    }
    if (w_idx == w_len) {
         return (s_idx - w_idx);
    } else {
         return -1;
    }
}

void generate_next(const char * w, int * next) {
     int index = 0, k = -1;
     int w_len = strlen(w);
     next[0] = -1;
     while (index < w_len -1) {
         if (k == -1 || w[index] == w[k]) {
             ++k;
             ++index;
             next[index] = k;
         } else {
             k = next[k];
         }
     }
}

算法分析

注意到这里我们对于部分匹配表做了一些额外的处理，我们将部分匹配表的值向右移动了一位，并且将部分匹配表的第一个值置为了-1。

这是因为字符串w的第一个字符串的特殊性决定的，因为w字符的第一个字符串失配后无法回退，只能从s字符串的下一个字符开始匹配。

此外，在求解next数组的函数generate_next中还有一句k=next[k]，这实际上是字符串的自我匹配的过程，当0–k-1发生失配时，应当找到一个满足条件的j，从0–j-1之后继续匹配，直到找不到更小的字符串为止。

算法复杂度

O(m+n)

参考

从头到尾彻底理解KMP

【经典算法】——KMP，深入讲解next数组的求解

克努斯-莫里斯-普拉特算法

后记

一直不能够深刻地理解KMP算法，即使是写完了这篇Blog，我仍然对于KMP算法有着有限的了解，所以不排除这篇Blog还会有后续的可能。

评论和共享