KMP字符串匹配算法 – wiki基地

KMP 字符串匹配算法详解

KMP 算法，全称为 Knuth-Morris-Pratt 算法，是由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三位科学家共同提出的高效字符串匹配算法。相比于朴素的字符串匹配算法，KMP 算法能够有效避免重复的比较操作，从而显著提升匹配效率。本文将深入探讨 KMP 算法的原理、实现以及优化技巧。

1. 朴素字符串匹配算法的局限性

在理解 KMP 算法之前，我们先回顾一下朴素的字符串匹配算法。假设我们要在文本串 T 中查找模式串 P，朴素算法的基本思路是从 T 的第一个字符开始，逐个与 P 的第一个字符进行比较。如果匹配，则继续比较后续字符；如果不匹配，则将 P 向右移动一位，重新从 T 的下一个字符开始比较。

这种方法简单易懂，但在某些情况下效率低下。例如，考虑文本串 T = "ABABCABAB" 和模式串 P = "ABAB"。当 T[0...3] 与 P 匹配失败时，朴素算法会将 P 向右移动一位，然后从 T[1] 开始重新比较。然而，由于 P 的前两位 “AB” 已经与 T[0...1] 匹配，而 T[0...1] 又与 P 的后两位 “AB” 相同，因此从 T[1] 开始比较是多余的。KMP 算法正是针对这种冗余比较进行了优化。

2. KMP 算法的核心思想：利用模式串的自身信息

KMP 算法的关键在于预先计算一个 “部分匹配表”（Partial Match Table，PMT），也称为 “next 数组”。这个表存储了模式串 P 的每个前缀子串的最长公共前后缀的长度。

• 前缀子串: 指从模式串开头到某个位置结束的子串，不包含模式串本身。
• 后缀子串: 指从模式串某个位置开始到结尾结束的子串，不包含模式串本身。
• 公共前后缀: 指既是前缀子串又是后缀子串的子串。

例如，对于模式串 P = "ABABCABAB"：

• 前缀子串 “ABAB” 的最长公共前后缀是 “AB”，长度为 2。
• 前缀子串 “ABABCABA” 的最长公共前后缀是 “ABA”，长度为 3。

通过 next 数组，KMP 算法可以在匹配失败时，根据已匹配的部分信息，直接将模式串 P 移动到一个合适的位置，避免不必要的比较。

3. next 数组的计算方法

next 数组的计算是 KMP 算法的核心。其计算过程本质上也是一个字符串匹配的过程，只不过是模式串 P 与自身进行匹配。

具体步骤如下：

1. 初始化 next[0] = -1。
2. 初始化 j = -1，i = 1。j 表示当前最长公共前后缀的长度，i 表示当前正在计算 next 值的位置。
3. 循环直到 i 达到模式串 P 的长度：
   • 如果 P[i] == P[j+1]，则 next[i] = j + 1，i++，j++。
   • 如果 P[i] != P[j+1] 且 j > -1，则 j = next[j]，继续比较。
   • 如果 P[i] != P[j+1] 且 j == -1，则 next[i] = 0，i++。

4. KMP 匹配过程

利用计算好的 next 数组，KMP 算法的匹配过程如下：

1. 初始化 i = 0，j = 0。i 表示文本串 T 的当前位置，j 表示模式串 P 的当前位置。
2. 循环直到 i 达到文本串 T 的长度 或 j 达到模式串 P 的长度：
   • 如果 T[i] == P[j]，则 i++，j++。
   • 如果 T[i] != P[j] 且 j > 0，则 j = next[j-1]，继续比较。
   • 如果 T[i] != P[j] 且 j == 0，则 i++。
3. 如果 j 达到模式串 P 的长度，则匹配成功，返回匹配位置 i - j。否则，匹配失败，返回 -1。

5. KMP 算法的优化：nextval 数组

next 数组在某些情况下存在冗余比较。例如，对于模式串 P = "AAAA"，其 next 数组为 [-1, 0, 1, 2]。当 T[i] 与 P[3] 匹配失败时，j 会回溯到 next[2] = 1，然后比较 T[i] 与 P[1]。由于 P[3] = P[2] = P[1] = 'A'，因此这次比较也是多余的。

为了避免这种冗余比较，可以引入 nextval 数组。nextval 数组的计算方法是在 next 数组的基础上进行改进：

1. 初始化 nextval[0] = -1。
2. 对于 i = 1 到 P.length - 1：
   • 如果 P[i] != P[next[i-1]+1]，则 nextval[i] = next[i]。
   • 如果 P[i] == P[next[i-1]+1]，则 nextval[i] = nextval[next[i-1]]。

使用 nextval 数组代替 next 数组进行 KMP 匹配，可以进一步提高效率。

6. KMP 算法的复杂度分析

• 预处理阶段 (计算 next/nextval 数组): 时间复杂度为 O(m)，空间复杂度为 O(m)，其中 m 为模式串的长度。
• 匹配阶段: 时间复杂度为 O(n)，其中 n 为文本串的长度。

因此，KMP 算法的整体时间复杂度为 O(n+m)，空间复杂度为 O(m)。

7. KMP 算法的应用场景

KMP 算法广泛应用于各种字符串匹配场景，例如：

• 文本编辑器中的查找功能
• 生物信息学中的基因序列比对
• 网络安全中的病毒查杀
• 数据挖掘中的模式识别

8. 总结

KMP 算法通过预处理模式串，避免了朴素算法中的冗余比较，从而显著提高了字符串匹配的效率。理解 next 数组和 nextval 数组的计算方法是掌握 KMP 算法的关键。 KMP 算法作为一种经典的字符串匹配算法，在实际应用中具有重要的价值。 通过学习 KMP 算法，我们不仅可以提升字符串处理能力，还能更深入地理解算法的设计思想，为解决其他问题提供思路。