KMP算法 | Garry's Blog

KMP算法

Garry Xu 3月 07, 2022

以下笔记来自阅读：Knuth D E , Morris J H , Pratt V R . Fast Pattern Matching in Strings[J]. Siam Journal on Computing, 1977, 6(2):323-350.

文本编辑器软件经常需要在一串字符中查找以匹配特定的模式，这些模式也是一串字符，我们有时需要查找到所有匹配的位置，也有时候，仅仅需要获取第一个匹配位置。例如，c a t e n a r y 包含模式 t e n 。

最直接的查找方式是在文本的每一个位置开始查找，如果没有匹配，就放弃该次查找。但是这种方式可能非常低效，举个例子，比如我们需要查找 a a a a a a a a a a a a a a b 中出现的 a a a a a a a b。模式是 aⁿb, 文本是 a²ⁿb，我们将需要进行 (n+1)² 次比较。另外，这种传统处理方式在遍历输入字符串的时候需要回退，这将给我们频繁用到的缓存操作带来麻烦（想像从磁盘读取数据到内存缓存）。

本文将描述一种模式匹配算法，该算法可以在 O(m + n) 时间内，从长度为n的字符串中查找长度为m的模式字符串的所有出现位置，并且不需要回退输入文本。算法仅需要占用 O(m) 的额外内存空间，并且复杂度和文本使用的字符表大小无关。

我们首先来从一个低效但是容易理解的角度理解算法。

通俗理解

算法背后的想法从这个角度更会容易理解：想像我们将模式字符串放置在输入字符串之上，并且按照某种方式向右滑动模式字符串。比如：从 b a b c b a b c a b c a a b c a b c a b c a c a b c 中查找 a b c a b c a c a b。首先，我们将模式字符串放到最左侧，准备匹配输入字符串的第一个字符：

1
2
3

a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑

箭头指向当前的输入字符，由于其指向 b，与 a 不匹配，我们向右滑动一位，移动到下一个输入字符：

1
2
3

  a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
  ↑

现在我们匹配了一个字符，因此我们的模式字符串保持不动，继续扫描。很快，我们发现了另一个不匹配的字符：

1
2
3

  a b c a b c a c a b 
b a b c b a b c a b c a a b c a b c a b c a c a b c
        ↑

此时我们已经匹配了除第四个字符以外的前三个字符，所以我们知道，输入字符串的最后四个字符是 a b c x (x≠a)。我们不需要记录之前扫描过的字符串，因为我们目前在模式字符串中的位置就提供了重建这些字符串的足够信息。在上述的例子中，无论 x 是什么字符，只要不是 a, 我们可以直接将模式字符串右移4位，因为一位、两位、三位的移动都不可能匹配字符串。

1
2
3

          a b c a b c a c a b 
b a b c b a b c a b c a a b c a b c a b c a c a b c
          ↑

很快我们遇到另一个部分匹配，这次在模式字符串的第八个字符。

1
2
3

          a b c a b c a c a b 
b a b c b a b c a b c a a b c a b c a b c a c a b c
                        ↑

现在，我们知道输入字符串的的最后八个字符是：a b c a b c a x (x≠c)，模式字符串因此应该右移三位。

1
2
3

                a b c a b c a c a b 
b a b c b a b c a b c a a b c a b c a b c a c a b c
                        ↑

我们尝试重新匹配，但是这次也失败了，因此我们再次将模式字符串右移四位。继续扫描，我们在第八位遇到了不匹配的情况。

1
2
3

                        a b c a b c a c a b 
b a b c b a b c a b c a a b c a b c a b c a c a b c
                                      ↑

再次右移三位；这次我们找到了第一个匹配位置，我们最终完成了匹配。

1
2
3

                              a b c a b c a c a b 
b a b c b a b c a b c a a b c a b c a b c a c a b c
                                                ↑

上述一步一步的描述表明，当我们在模式字符串的第j个字符 pattern[j] 发现不匹配时，如果有一个辅助表能够刚好告诉我们如何滑动模式字符串，模式匹配的过程将变得非常高效。让 next[j] 代表在发生不匹配时模式字符串需要检查的下一个字符位置。因此在不匹配时，相对于输入文本，我们可以向右滑动模式字符串 j - next[j] 位。下述表格列出来了正确的值：

         j = 1 2 3 4 5 6 7 8 9 10

pattern[j] = a b c a b c a c a b

   next[j] = 0 1 1 0 1 1 0 5 0 1 

注意： next[j] = 0 代表将模式字符串直接滑过当前的输入字符

我们后面将讨论如何计算 next[j]; 幸运的是，计算过程很简单，只需要 O(m) 步骤。

在每步的扫描过程中，我们要么移动输入文本的指针，要么移动模式字符串，两者都最多能移动 n 次；因此，在构建 next 表后，最多需要 2n 步。当然模式字符串并没有真正的移动，只需要维护好指针 j 即可。

算法实现

模式匹配的过程可以描述为如下形式：

place pattern at left;
while pattern not fully matched
      and text not exhausted do
      begin
      while pattern character differs from
            current text character
            do shift pattern appropriately;
            advance to next character of text;
      end;

便于描述，让我们假设输入文本用数组 text[1:n] 描述，模式字符串用 pattern[1:m] 描述。我们假设 m > 0 ，也就是模式字符串不为空。k 和 j 是整数变量，text[k] 是当前的文本字符，pattern[j] 是当前模式字符串字符；模式字符串目前放置在输入文本 p + 1 到 p + m 的位置上，k = p + j。于是，上面的描述，可以简化为：

j := k := 1;
while j ≦ m and k ≦ n do
    begin
    while j > 0 and text[k] ≠ pattern[j]
        do j := next[j];
    k := k + 1; j := j + 1;
    end;

如果最后程序结束 j > m，则找到了模式字符串的第一个匹配位置，k - m 到 k - 1。但是如果 j ≦ m，表明输入文本已经遍历完，但是没有发现匹配。这个程序有一个有趣的特性，内部循环的 j := next[j]; 操作执行不如外面的 k := k + 1 频繁；实际上，内部循环一般情况都执行的不频繁，因为外面的文本指针移动要比模式字符串的右移频繁的多。

为了严格证明上述程序的正确性，使用如下不变关系（invariant relation）：Let p = k - j (恰好位于和模式字符串对齐的前一个文本字符)，我们有 text[p + i] = pattern[i] for 1 ≦ i < j (当j > 0时，我们已经匹配了前面的j - 1个字符); 但是对于 0 ≦ t < p 有 text[t + i] ≠ pattern[i] for some i, 1 ≦ i ≦ m（在 p 之前不可能有对模式的完全匹配）。

程序要想正确是建立在能够计算 next 表之上的，只有这样，我们才能在做了 j := next[j] 的变换之后，依然保持上面的关系成立。现在，让我们看看如何计算 next 表。当程序设置 j := next[j]，我们知道 j > 0，输入文本包含 text[k] 的最后 j 个字符是：

1	pattern[1] ... pattern[j - 1] x , x ≠ pattern[j]

我们想要的是找到最少的右移步数，并且有可能匹配当前的输入字符。换句话说，我们想要找到最大的 i （i < j) 能够使得最后的 i 个输入字符是：

1	pattern[1] ... pattern[i] x , pattern[i] ≠ pattern[j]

（如果没有这样的 i，next[j] = 0）。按照如上 next[j] 的定义，很容易可以得到：text[t + 1]...text[k] ≠ pattern[1]...pattern[k - t], for k - j ≦ t < k - next[j]。因此前述的不变关系得到了保持，我们程序的正确性也得到了保证。

现在让我们来解决一直推迟的一个问题，如何计算 next[j]。如果在定义 next[j] 时我们不要求 pattern[i] ≠ pattern[j]，这个问题将变得简单一些，因此我们先优先考虑这个简化的场景。让 f[i] 代表满足如下条件的最大的 i (i < j):

1	pattern[1]...pattern[i - 1] = pattern[j - i + 1]..pattern[j - 1]

因为这个条件当 i = 1 时总是满足，因此对于 j > 1 有 f[j] ≥ 1。按照惯例，我们让 f[1] = 0。示例1中的模式字符串有如下的 f 表：

1
2
3

         j = 1 2 3 4 5 6 7 8 9 10 
pattern[j] = a b c a b c a c a b
      f[j] = 0 1 1 1 2 3 4 5 1 2

如果 pattern[j] = pattern[f[j]]，那么 f[j + 1] = f[j] + 1；如果两者不相同，我们可以将 text 替换为 pattern 复用上述的模式匹配算法计算 f[j +1] 。（注意计算 f[j] 问题与模式匹配算法在不变关系上的共同之处。我们的程序计算最大的小于k 的 j，满足 pattern[1]..pattern[j -1] = text[k - j + 1]..text[k -1]，所以我们可以将之前的算法用在当前的问题上）。假设 f[j] 和 next[1]...next[j-1] 都已经计算完成，下面的程序将计算 f[j + 1] ：

t := f[j];
while t > 0 and patter[j] ≠ pattern[t] 
    do t := next[t];
f[j + 1] := t + 1;

程序的正确性如前面的分析；可以想像两份模式字符串的拷贝，一个相对于另一个向右侧滑动。例如，假设在上面的例子中我们已经计算得出 f(8) = 5，让我们看看如何计算 f(9)。此时视图如下：

1
2
3

      a b c a b c a c a b
a b c a b c a c a b
              ↑

由于 pattern[8] ≠ b, 我们把上面的拷贝字符串右移，在移动的过程中，我们已经知道最近扫描过的字符串是 a b c a x 且 x ≠ b, next 表已经告诉我们下一步要要移动，于是得到：

1
2
3

              a b c a b c a c a b
a b c a b c a c a b
              ↑

我们又一次遇到了不匹配的情况，下一步的移动使 t = 0，因此我们得到 f[9] = 1。

当我们知道如何计算 f[j]，离计算 next[j] 也就一步之遥了。对比两者的定义我们可以得到，对于 j > 1:

$next[j]= \begin{equation*} \left\{ \begin{aligned} f[j],\qquad&if pattern[j] ≠ pattern[f[j]] \\ next[f[j]],\qquad&if pattern[j] = pattern[f[j]] \end{aligned} \right. \end{equation*}$

因此我们可以用如下的算法计算 next 表，其中也不需要存储 f[j]:

j := 1; t := 0; next[1] := 0;
while j < m do
    begin comment t = f[j]
        while t > 0 and pattern[j] != pattern[t] 
            do t := next[t]
        t := t + 1; j := j + 1;
        if pattern[j] = pattern[t]
        then next[j] := next[t];
        else next[j] := t;
    end

这个程序的时间复杂度是 O(m)，原因和之前模式匹配算法 O(n)的一样：内部循环中的t := next[t] 永远将上层的模式字符串向右移动，因此最多能够执行 m 次。（另一个不同的证明复杂度与 m 线性相关的方法是变量t从0开始，增加了 m - 1 次的1；t值永远都是正值，因此降低t值的这个操作 t := next[t]，最多也就能执行 m - 1 次）

来总结一下，文本字符串可以使用两种思想来实现高效搜索：我们可以提前计算好需要的右移步数，这样当第 j 位发生不匹配时，我们可以按照计算结果进行移动；另外，对右移步数的计算是很高效的，同样可以应用模式匹配算法的思想：右移模式匹配字符串自己。