KMP 算法
第 1 页 共 5 页
Knuth-Morris-Pratt（KMP）算法（字符串匹配）
1 问题
我们的问题是要去判断一个小字符串（或称模式，Pattern，简记作 P，长度为 m）是否
出现在一个长字符串（或称文本，Text，简记作 T，长度为 n）中。一些简单的算法仅移动
P，而且会忘记之前已经匹配的符号的信息，这样算法可能会让 T 中的每一个字符与 P 中的
每一个符号进行比较。这种做法的复杂度是最差的
()nm
。
Knuth, Morris and Pratt 算法【KMP 77】利用了先前字符比较中获得的信息，若 T 中的
字符已经与 P 中的某一个字符匹配上，它不会再被拿去与 P 中的字符做比较。因此，KMP
算法在搜索阶段的复杂度是 O(n)。
此时有必要对 P 做预处理，以取得内部结构信息。预处理阶段的复杂度是 O(m)。因为
mn ，因此 KMP 算法的复杂度就是 O(n)。
1.1 查找算法实例
让我们用一个实例来演示这个算法。在任意给定时间，本算法被两个整数 i 和 j 所决
定： i 代表 T 内当前查找位置；j 代表 P 当前做比较的字符位置。图示如下：
i: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
j: 0123456
我们从 P 与 T 的开头比较起。我们比对到 T[3](=' ') 时，发现 P[3](='D') 与其不符。接着
并不是从 T[1]比较下去。我们已经知道 T[1]~T[3] 不与 P[0] 相合。因此，略过这些字符，令 i
= 4 以及 j = 0。
i: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
j: 0123456
如上所示，我们检核了 "ABCDAB" 这个字符串。然而，这与目标仍有些差异。我们可
以注意到，"AB"在字符串头尾处出现了两次。这意味着尾端的 "AB" 可以作为下次比较的起
始点。因此，我们令 i = 8, j = 2，继续比较。图标如下：
i: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
j: 0123456
于 i = 10, j = 2 的地方，又出现不相符的情况。类似地，令 i = 11, j = 0 继续比较：
i: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
评论0