Post

String - KMP Algorithm

本文详细介绍了KMP（Knuth-Morris-Pratt）字符串匹配算法，帮助读者深入理解其高效的工作原理。KMP算法通过预处理模式串，构建部分匹配表（PMT）和next数组，能够在匹配过程中跳过不必要的比较，从而避免主串指针回退，显著提高匹配效率。

Posted Updated
By Zenith
views 29 min read
String - KMP Algorithm

字符串匹配是计算机的基本任务之一。举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE“，我们想知道，里面是否包含另一个字符串”ABCDABD“？许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。虽然 KMP 算法高效且经典，但由于逻辑稍微复杂，理解起来并不容易。本文将用通俗的语言，为你拆解 KMP 算法的核心思想和应用。

低效的暴力匹配算法

首先，我们来看一个简单但低效的字符串匹配方法：暴力匹配。

1
2
3
4
5
6
7
8
9
10

0007 int match ( char* P, char* T ) { //串匹配算法（Brute-force-1）
0008    int n = strlen ( T ), i = 0; //文本串长度、当前接受比对字符的位置
0009    int m = strlen ( P ), j = 0; //模式串长度、当前接受比对字符的位置
0010    while ( (j < m) && (i < n) ) //自左向右逐个比对字符
0011       if ( T[i] == P[j] ) //若匹配
0012          { i ++;  j ++; } //则转到下一对字符
0013       else //否则
0014          { i -= j - 1; j = 0; } //文本串回退、模式串复位
0015    return i - j; //如何通过返回值，判断匹配结果？
0016 }

假设主串为 “BBC ABCDAB ABCDABCDABDE“，模式串为 “ABCDABD“。

  • 首先，从主串的第一个字符 B 开始，与模式串的第一个字符 A 进行比较。发现不匹配，则模式串整体向右移动一位。

    1
2
3

      BBC ABCDAB ABCDABCDABDE
  |
  ABCDABD

  • 第一个字符匹配失败了，继续比较主串中的下一个字符 B 和模式串的第一个字符 A。仍然不匹配，模式串再次整体右移一位。

    1
2
3

      BBC ABCDAB ABCDABCDABDE
   |
   ABCDABD

  • 就这样，直到主串中的字符 A 与模式串的第一个字符 A 匹配时，才继续比较主串和模式串的后续字符。

    1
2
3

      BBC ABCDAB ABCDABCDABDE
      |
      ABCDABD

  • 下一步，接着比较主串和模式串的下一个字符，在这个例子中，下一个字符还是相同。

    1
2
3

      BBC ABCDAB ABCDABCDABDE
       |
      ABCDABD

  • 直到字符串有一个字符，与搜索词对应的字符不相同为止。

    1
2
3

      BBC ABCDAB ABCDABCDABDE
            |
      ABCDABD

  • 这时，最自然的反应是，将模式串整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。尤其当模式串较长且主串包含大量重复字符时，性能会进一步下降。

    1
2
3

      BBC ABCDAB ABCDABCDABDE
       |
       ABCDABD

KMP 算法的基本思想

KMP 算法的核心思想是避免重复比对，利用模式串的部分匹配信息来提高效率。通过预处理模式串，构建一张《部分匹配表》（Partial Match Table），算法可以在匹配失败时“记住”已经匹配的信息，从而不需要将主串回退。以下是详细的解析：

1
2

PATTERN: ABCDABD
TABLE:   0000120

已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照公式移动位数 = 已匹配的字符数 - 对应的部分匹配值算出向后移动的位数：移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 = 4，所以将搜索词向后移动4位。

1
2
3

BBC ABCDAB ABCDABCDABDE
            |
        ABCDABD

空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

1
2
3

BBC ABCDAB ABCDABCDABDE
            |
            ABCDABD

因为空格与A不匹配，继续后移一位。逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

1
2
3

BBC ABCDAB ABCDABCDABDE
                    |
            ABCDABD

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

部分匹配表的生成

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。”部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

字符串前缀集合后缀集合共有元素长度
A[][]-0
AB[A][B]-0
ABC[A, AB][BC, C]-0
ABCD[A, AB, ABC][BCD, CD, D]-0
ABCDA[A, AB, ABC, ABCD][BCDA, CDA, DA, A]A1
ABCDAB[A, AB, ABC, ABCD, ABCDA][BCDAB, CDAB, DAB, AB, B]AB2
ABCDABD[A, AB, ABC, ABCD, ABCDA, ABCDAB][BCDABD, CDABD, DABD, ABD, BD, D]-0

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

可能说到这里，你或许懂了部分匹配表的工作原理，但是还是比较难想象出来具体前后缀和部分匹配表为什么能够实现我们要的快速定位，他们是怎么扯上关系的？这里我再用图来形象的进行解释。如下图

nexttable

以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。

PMT 和 next 的关系

到这里，请保证你已经理解了部分匹配表（PMT）的原理以及作用，因为next是与部分匹配表息息相关，甚至可以这么说，next就是部分匹配表。

有了上面的思路，我们就可以使用PMT加速字符串的查找了。我们看到如果是在模式串的 j 位 失配，那么影响 j 指针回溯的位置的其实是第 j − 1 位的 PMT 值，所以为了编程的方便， 我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。这样，我们可以得到PMT和next数组的关系，我们用模式串“abababca”来举例，并求出PMT值和next数组，表如下：

1
2
3

char:  a  b  a  b  a  b  c  a
PMT:   0  0  1  2  3  4  0  1
next: -1  0  0  1  2  3  4  0

其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。到这里，我们知道了PMT和next数组的关系，这个时候，我想先给出，在有next数组的帮助下，我们如何进行匹配的代码实现，这样有助于我们认识清楚next数组在KMP算法中的重要性。

1
2
3
4
5
6
7
8
9
10
11
12

int match ( char* P, char* T ) {  //KMP算法
   int* next = buildNext ( P ); //构造next表
   int n = ( int ) strlen ( T ), i = 0; //文本串指针
   int m = ( int ) strlen ( P ), j = 0; //模式串指针
   while ( (j < m) && (i < n) ) //自左向右逐个比对字符
      if ( 0 > j || T[i] == P[j] ) //若匹配，或P已移出最左侧（两个判断的次序不可交换）
         { i ++;  j ++; } //则转到下一字符
      else //否则
         j = next[j]; //模式串右移（注意：文本串不用回退）
   delete [] next; //释放next表
   return i - j;
}

next 数组的构造

到这里，其实KMP的基本主体就已经讲完了，你会发现，其实KMP算法的动机是很简单的，解决的方案也很简单。不过我们还有一个疑问，就是next数组我们要怎么用代码去求解呢？

next

经过前面的讲解，我们都知道next数组都是通过PMT转化过来的，而PMT的求解，是通过前后缀的最长公共元素长度来完成的，那么我们有没有很好的求解next数组的方法呢（这里就把next当做PMT的求解了）。现在，我们再看一下如何编程快速求得next数组。其实，求next数组的过程完全可以看成模式串自行进行字符串匹配的过程，即以模式（就是pattern）字符串为主字符串，以模式字符串（就是pattern）的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。

具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算（因为i=0时，pmt系数为0，在next中，next[-1]我们就直接给-1，前面我们有说过）。 在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示。（这一段可能不太好理解，结合代码来理解）。

  • 首先比较i = 1，j = 0的位置，发现两个不相等，按照上面的说的规则， i和j处的字符不相匹配，所以长度为0。

    1
2
3
4
5
6
7

      next[2] = 0
    i
    |
  a b a b a b c a
    a b a b a b c a
    |
    j

  • 然后i++，j回到0，继续进行比较，发现 i 和 j 处的字符相匹配，长度为1。

    1
2
3
4
5
6
7

      next[3] = 1
      i
      |
  a b a b a b c a
      a b a b a b c a
      |
      j

  • 这个时候，由于上一个是相等的，所以进行了i++，j++的操作，然后进行比较，发现 i 和 j 处的字符相匹配，长度为2。

    1
2
3
4
5
6
7

      next[4] = 2
        i
        |
  a b a b a b c a
      a b a b a b c a
        |
        j

  • 按照上一步同样的规则，我们一直匹配到i = 6，j = 4，发现两个不相等，所以长度为0。

    1
2
3
4
5
6
7

      next[6] = 4
            i
            |
  a b a b a b c a
      a b a b a b c a
            |
            j

  • 到了i= 7，发现i，j两处的两个字符不相匹配了，这个时候，按照i++，j 回到0的操作继续匹配

    1
2
3
4
5
6
7

      next[7] = 0
              i
              |
  a b a b a b c a
              a b a b a b c a
              |
              j

出现的情况就上面这些，然后按照上面的规则，一直匹配到结束为止。下面贴出代码，最好就是结合代码过去进行手动运行一遍，加深理解。

1
2
3
4
5
6
7
8
9
10

int* buildNext ( char* P ) { //构造模式串P的next表
   int m = strlen ( P ), j = 0; //“主”串指针
   int* next = new int[m]; int t = next[0] = -1; //next表，首项必为-1
   while ( j < m - 1 )
      if ( 0 > t || P[t] == P[j] ) { //匹配
         ++t; ++j; next[j] = t; //则递增赋值：此处可改进...
      } else //否则
         t = next[t]; //继续尝试下一值得尝试的位置
   return next;
}

next 数组的优化

如果你已经理解了前面提到的内容，那么恭喜你，KMP 算法的基础部分已经学完了！不过，基础并不等于完整，因为我们提到的 next 数组还有优化的空间。那么，优化后的 next 数组又是如何实现的呢？接下来，我们将以一个具体的例子来说明优化的原理和方法。

优化前的 next 数组问题

假设模式串是 "abab"，按照之前的方法构造 next 数组，可以得到：

1

next = [-1, 0, 0, 1]

现在用此模式串和文本串 "abacababc" 进行匹配：

  1. P[3] 和 S[3] 不匹配（即 b != c），模式串向右移动 j - next[j] 位，此时 j = 3，next[3] = 1，移动 3 - 1 = 2 位。
  2. 右移两位后，P[next[3]] = P[1] = b 再次与 S[3] = c 进行匹配，这必然失败，因为我们已经知道 P[3] = b 和 S[3] 不匹配。

问题出在 next[3] 的值上：next[3] 指向了与 P[3] 相同的字符 P[1]，导致重复失配。

为了避免这种重复失配的情况，我们需要优化 next 数组，确保 P[next[j]] != P[j]。如果在计算 next 数组时发现 P[next[j]] = P[j]，则递归地设置 next[j] = next[next[j]]。

优化后的 next 数组求解

下面是优化后的 next 数组求解代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

int* buildNext ( char* P ) { //构造模式串P的next表（改进版本）
   int m = strlen ( P ), j = 0; //“主”串指针
   int* next = new int[m]; int t = next[0] = -1; //next表，首项必为-1
   while ( j < m - 1 )
      if ( 0 <= t && P[t] != P[j] ) //失配
         t = next[t]; //继续尝试下一值得尝试的位置
      else //匹配
         if ( P[++t] != P[++j] ) //附加条件判断
            next[j] = t; //唯当新的一对字符也匹配时，方照原方法赋值
         else
            next[j] = next[t]; //否则，改用next[t]（此时必有：P[next[t]] != P[t] == P[j]）
   return next;
}

以模式串 "abab" 为例，按照优化后的算法，可以得到新的 next 数组：

1

next = [-1, 0, -1, 0]

通过对比优化前后的 next 数组，我们可以发现优化后的数组避免了重复失配的情况。

如何快速心算优化后的 next 数组？

如果已经计算出了原始的 next 数组，可以很容易地心算出优化后的值。规则如下：

  • 如果出现 P[next[j]] = P[j] 的情况，则设置 next[j] = next[next[j]]，直到不满足 P[next[j]] = P[j]。

接下来，咱们继续拿之前的例子说明，整个匹配过程如下：

  1. 原始 next 数组：[-1, 0, 0, 1]
  2. 优化步骤：
    • next[2] = 0，但 P[next[2]] = P[0] = a 和 P[2] = a 相同，递归设置：next[2] = next[next[2]] = next[0] = -1。
    • next[3] = 1，但 P[next[3]] = P[1] = b 和 P[3] = b 相同，递归设置：next[3] = next[next[3]] = next[1] = 0。

最终得到优化后的 next 数组：[-1, 0, -1, 0]。

优化后的匹配过程

接下来，使用优化后的 next 数组，匹配主串 "abacababc" 和模式串 "abab"。

  • S[3]与P[3]匹配失败。

    1
2
3

       a b a c a b a b c
   a b a b
  -1 0 -1 0

  • S[3]保持不变，P的下一个匹配位置是P[next[3]]，而next[3]=0，所以P[next[3]]=P[0]与S[3]匹配。

    1
2
3

       a b a c a b a b c
         a b a b
        -1 0 -1 0

  • 由于上一步骤中P[0]与S[3]还是不匹配。此时i=3，j=next [0]=-1，由于满足条件j==-1，所以执行“++i, ++j”，即主串指针下移一个位置，P[0]与S[4]开始匹配。最后j==pLen，跳出循环，输出结果i - j = 4（即模式串第一次在文本串中出现的位置），匹配成功，算法结束。

    1
2
3

       a b a c a b a b c
           a b a b
          -1 0 -1 0

时间复杂度：O(n + m) 的分摊分析

KMP 算法之所以高效，是因为它避免了重复比对，能够在 O(n + m) 的时间复杂度内完成字符串匹配任务（其中，n 是主串长度，m 是模式串长度）。为了更好地理解这一点，我们通过以下两种分析方法——聚合分析（Aggregate Analysis） 和 记账分析（Accounting Analysis），来详细解释为什么 KMP 算法能够达到这一复杂度。

聚合分析 (Aggregate Analysis)

通过构造一个计步器 k，它随着算法的迭代而递增，用于记录主串和模式串的操作步数。我们可以证明算法的时间复杂度为 O(n + m)。

1

k = 2 * i - j
  • i 是主串指针的位置。
  • j 是模式串指针的位置。

迭代中的增量规则: 在 KMP 算法中，每次迭代时：

  1. 如果匹配成功（T[i] == P[j] 或 j < 0），则指针 i 和 j 同时向右移动：
    1
2

    i++;
j++;

    此时，k 的值增加 1。

  2. 如果匹配失败（T[i] != P[j]），则模式串指针 j 根据 next[j] 回退：
    1

    j = next[j];

    即使发生回退，k 的值也至少增加 1。

初始与终止条件

  • 初始状态：k = 0，此时 i = 0，j = 0。
  • 结束状态：当匹配完成或主串匹配结束时，k = 2 * i - j。

由于 i 最大值为 n（主串长度），j 的最小值为 -1（next[0] 的值），我们可以得出：

1

k = 2 * i - j ≤ 2 * (n - 1) - (-1) = 2n - 1

因此，迭代总次数的上界为 2n - 1，而这正是 O(n) 的数量级。

记账分析 (Accounting Analysis)

记账分析是另一种常用方法，用于解释复杂度中的分摊成本。KMP 的复杂度由两部分构成：

  1. 成功比对的成本

    成功比对的成本是指主串中的每个字符与模式串中某个字符进行比较时，能够正确匹配的情况。每次成功比对都会将主串指针 i 向前移动一次，因此 成功比对的总次数最多为 n（即主串长度）。每次成功比对，在主串的比对操作上记账一次，共计 O(n)。

  2. 失败比对的成本

    失败比对的成本稍显复杂，因为在匹配失败时，模式串的指针 j 会根据 next 表发生跳跃，而主串指针 i 不会回退。这种跳跃虽然会多次发生，但对同一个位置 i，每个字符最多只能进行一次失败的比对。失败比对的成本可以通过对 next 表的性质进行分析得出：每次失败时，j 会跳到 next[j]，即回到模式串中一个较短的匹配位置。模式串指针 j 的总跳跃次数，等价于模式串的所有后缀的跳跃步数之和。每次失败比对，在模式串的跳跃操作上记账一次，共计 O(m)。

由于模式串的跳跃次数只依赖于其自身的长度（即 m），且每次失败操作与 next 表的计算相关，整个失败比对过程的复杂度为 O(m)。成功比对和失败比对的总成本为：

1

总复杂度 = O(n) + O(m) = O(n + m)

总结

KMP 算法的优化主要体现在 next 数组的改进，通过避免 P[next[j]] = P[j] 的情况，减少了无意义的重复匹配。优化后的 next 数组不仅提高了匹配效率，同时让算法更加稳定。

优化后的优点

  • 时间复杂度：整体复杂度仍然是 O(n + m)，但优化后减少了重复计算的情况。
  • 适用性更强：对于具有重复前缀和后缀的模式串，优化后的算法表现更加高效。

掌握 KMP 算法及其优化方法，不仅能加深对字符串匹配问题的理解，也能为解决其他模式匹配问题提供思路！

Computer Science and Technology, Data Structure and Algorithm
algorithms data-structures string-matching kmp tsinghua
This post is licensed under CC BY 4.0 by the author.