date: 2016-03-08
categories: Algorithms
tag: [String matching, 字符串匹配, KMP]
mathjax: true
博客

title: 字符串匹配-KMP算法

前言

这篇是字符串匹配的第二篇，如果你没有看过第一篇，你可以点击这里先看下第一篇的内容。

KMP算法全称是Knuth-Morris-Pratt，分别是联合发表该算法的三个计算机科学家的名字。此算法的核心是通过运用对这个模式在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符[1]。

暴力匹配（Brute force）

匹配以上P与T，其中P在T中出现两次（红色箭头指向位置）。

我们首先来看看暴力匹配算法的步骤：
1. 定义指针i和j分别指向P[0]和T[0]；
2. 匹配P[i]和T[j]；
3. 如果匹配，但$i \neq m - 1$，那么i和j各自+1，并回到步骤2继续匹配下个字符；
4. 如果匹配，且$i = m - 1$，那么P匹配，输出P[0]指向的位置；
5. 如果不匹配或者匹配已完成，j+1指向T的下一个字符，i回到0重新开始匹配P。

通常我们使用 m 表示 P 的长度，n 表示 T 的长度。

图例

1. 定义指针i和j分别指向 P[0] 和 T[0]；
2. 匹配 P[i] 与 T[j]；

3. 如果匹配，但$i \neq m - 1$，那么 i 和 j 各自+1，并回到步骤 2 继续匹配下个字符；

4. 如果匹配，且$i = m - 1$，那么 P 匹配，输出 P[0] 指向的位置；

如果出现不匹配，则

5. 如果不匹配或者匹配已完成，$j+1$ 指向 T 的下一个字符，i 回到0重新开始匹配 P。

分析

由于我们每次只把P往后挪动一个位置，所以P总共的挪动位置就是n次。而每次挪动后我们都进行最多m次的匹配，所以暴力匹配算法的时间复杂度是$O(n*m)$。

实际上当T剩余的长度比P短时，我们无需在往后移动P，因为那一定也不会匹配，也就是我们仅需往后移动 $n-m$ 次。但实际操作中，由于n常常远大于m，所以约等于n次。

你也许也会留意到，如果每次匹配P和T时都立马遇到不匹配，那么仅需$O(n)$次就能完成。即使不是立马都不匹配，也不可能每次都需要匹配m次的吧？没错，$O(n*m)$是worst case。更多关于平均时间复杂度的讨论，你可以点击这里。

KMP算法

部分匹配表（Partial Match Table）

既然每次只把P往后挪一个位置是不高效的，那么我们能不能每次挪动多个位置呢？

答案是肯定的！方式是通过充分利用以及“获得”的信息。在KMP算法中，这部分信息就是P本身的特征:

首先我们来观察P，不难发现当我们匹配到了字符ab后出现不匹配，那么将P往后移动一位无疑是肯定也不匹配的，因为我们知道$a \neq b$，所以更明智的做法是起码往后移动两位。

那么移动多少呢？

首先我们能够想到的将P往后挪到第一个字符也就是P[0]出现的位置。



在匹配到红框中四个字符后出现不匹配，那么我们将P后移两位，也就是移到T中再次出现a字符的位置。移动后仍然不匹配，我们再次将P移动两位直至T中出现字符a。

观察上面的过程，我们可以发现第二次的移动看似没有意义。但实际上c虽然不与P[4](从0开始)匹配，但有可能与P[3]匹配。我们觉得无意义的原因是因为我们知道c仅与P[8]匹配。那有没有办法可以根据已经匹配过的这些字符，计算出不影响匹配率的最大移动量呢？

答案是可以，方式是：部分匹配表（Partial Match Table）

部分匹配表可以称为next function，不同的KMP算法实现可能会导致next值不同，有些是从0开始，而这里我们是从-1开始的。思路是一样的，只是对齐的字符错一位而已。

思路

由于部分匹配表或者next function仅与P本身有关，与T无关，也就是说我们可以事先计算好部分匹配表的值。那么假设我们已经有next值的情况，KMP算法的步骤为：
1. 定义指针i和j分别指向P[0]和T[0]；
2. 匹配P[i]和T[j]；
3. 如果匹配，但$i \neq m - 1$，那么i和j各自+1，并回到步骤2继续匹配下个字符；
4. 如果匹配，且$i = m - 1$，那么匹配，输出P[0]指向的位置；
5. 如果不匹配，i赋值为不匹配的P字符的next值并从P[next]开始匹配P；
6. 如果完全不匹配或者匹配已完成，j+1指向T的下一个字符，i赋值为P最后一个字符的next值并从P[next]开始匹配P。

该算法思路在于只对 T 中的每个字符进行一次成功匹配！

PseudoCode

i:= -1;
for j:=0 to n-1 do:
    1. while i>= 0 and P[i+1] != T[j] {i := next(i)};
    2. if P[i + 1] = T[j] {i := i + 1};
    3. if i = m {output j - m + 1; i = next(i)};

图例

假设我有以上P，以及不知道怎么得到的next值（下一小节会介绍如何求next值）。

在匹配了四个字符后我们在P[4]位置遇到不匹配，我们通过查部分匹配表得知P[4]的next值为2。所以我们将$i = 2$并开始匹配P[i]和T[j]。

挪到2的意思，表示P前两个字符是一定匹配的，不需要进行对比。而P[2] $\neq$ T[4]。查表得next(P[2]) = 0，所以我们将$i = 0$并开始匹配P[i]和T[j]。

仍然不匹配。查表得next(P[0]) = -1，将$i=-1$，即将模式挪到T[j+1]位置，并开始匹配P[i]和T[j]。

完全匹配，查表得next(P[9]) = 0，所以我们将$i = 0$并开始匹配P[i]和T[j]。

如此类推直到完成所有的文本匹配。

分析

KMP算法的时间分析看似无从下手，但是其实不难发现，P每次都只会往后挪动而不会往左挪动，也就是说P最多只能右移$n-1$次，所以时间复杂度为$O(n)$。

部分匹配表计算

从上图以及部分匹配表的实际应用我们不难发现，其实next(i)值实际上是P[i]字符在之前匹配的最大的数字。

举个例子，上图中next(P[4]) = 2，是因为aba(P[2]~P[4])匹配aba(P[0]~P[2])。同理，因为ababab(P[2]~P[7])匹配ababab(P[0]~P[5])可以对导出next(P[7]) = 5。

参考与其他

[1]: KMP算法 - 维基

• 字符串匹配的KMP算法 by 阮一峰