KMP字符串匹配算法

数据结构与算法专题 · 线性时间字符串匹配的经典算法

专题：数据结构与算法系统学习

关键词：数据结构, 算法, KMP, 字符串匹配, 前缀函数, next数组, 线性时间, 模式匹配, 循环节

一、算法概述

KMP算法（Knuth-Morris-Pratt算法）是由Donald Knuth、Vaughan Pratt和James H. Morris三位计算机科学家于1977年联合提出的字符串匹配算法。KMP算法的核心突破在于：它能够在O(n+m)的时间复杂度内完成字符串匹配，其中n是文本串长度，m是模式串长度。这一线性时间的性能相比于朴素匹配算法的O(n*m)是一个巨大的飞跃，为字符串处理领域奠定了重要的基础。

核心思想：KMP算法利用已经匹配成功的部分信息，通过预处理模式串构建前缀函数（next数组），在匹配失败时将模式串有效地"跳过"已匹配的部分，从而避免文本串指针的回溯，实现线性时间的匹配效率。

为什么需要KMP算法？

在计算机科学中，字符串匹配是最基础也是最重要的操作之一。从文本编辑器的查找功能，到生物信息学中的DNA序列比对，再到网络入侵检测系统中的模式识别，字符串匹配无处不在。朴素匹配算法在最坏情况下需要对文本串进行大量的回溯操作。例如，在文本串"AAAAAAAAAAAAAAAAAB"中查找模式串"AAAAB"时，朴素算法几乎在每个位置都要比较到模式串的最后一个字符才失败，导致实际比较次数接近n*m。KMP算法正是为了解决这一效率瓶颈而生。

前置知识：学习KMP算法需要了解字符串的基本概念（子串、前缀、后缀、前后缀等），以及基础的数组操作和循环逻辑。具备基本的Python或C语言编程能力即可。

二、朴素匹配与KMP的对比

为了深入理解KMP算法的优势，我们首先来看朴素匹配算法是如何工作的，以及它存在哪些问题。

朴素匹配算法

朴素匹配的思路非常直观：将模式串与文本串的每个位置对齐，逐字符比较。如果匹配失败，模式串右移一位，重新从模式串的第一个字符开始比较。

朴素匹配的Python实现

def naive_search(text, pattern): n, m = len(text), len(pattern) positions = [] for i in range(n - m + 1): j = 0 while j < m and text[i + j] == pattern[j]: j += 1 if j == m: positions.append(i) return positions

朴素匹配的问题

上述代码虽然简单直观，但存在严重的效率问题：当匹配失败时，i只前进1，j回退到0，完全忽略了已经匹配成功的部分中蕴含的信息。例如，当模式串"ABABAC"与文本串"ABABABAC"匹配到第5个字符时失败，此时我们已经知道文本串的前5个字符是"ABABA"，而朴素算法会丢弃这些信息，仅将i加1后重新开始，造成了大量的重复比较。

朴素匹配的缺陷

  • 文本串指针i频繁回溯
  • 忽略已匹配部分的信息
  • 最坏时间复杂度O(n*m)
  • 大量重复比较操作

KMP的改进

  • 文本串指针i永不回溯
  • 充分利用已匹配信息
  • 时间复杂度O(n+m)
  • 每个字符至多比较两次

时间复杂度对比

算法 预处理时间 匹配时间 总时间复杂度 空间复杂度
朴素匹配 无 O(n*m) O(n*m) O(1)
KMP算法 O(m) O(n) O(n+m) O(m)
Boyer-Moore O(m+sigma) O(n/m)~O(n*m) O(n+sigma)~O(n*m) O(m+sigma)
Rabin-Karp O(m) O(n)平均 / O(n*m)最坏 O(n+m)平均 O(1)

三、前缀函数（Prefix Function / π数组）

前缀函数（也称为next数组或pi数组）是KMP算法的核心预处理产物。前缀函数π[i]的定义是：对于模式串pattern[0..i]这个子串，其最长的相等前后缀的长度。换言之，π[i]表示pattern[0..i]中，既是其前缀又是其后缀的最长子串的长度（注意，这个子串不能是整个串本身）。

严格定义：π[i] = max{k | 0 ≤ k < i+1 且 pattern[0..k-1] = pattern[i-k+1..i]}，即pattern[0..i]的最长的真前缀等于真后缀的长度。若不存在这样的k，则π[i] = 0。

前缀函数示例

以模式串"ABABAC"为例，我们来手动计算其π数组的值：

i pattern[i] 子串pattern[0..i] 最长的相等前后缀 π[i]
0 A "A" 无（不能是整个串） 0
1 B "AB" 无 0
2 A "ABA" "A"（前缀A=后缀A） 1
3 B "ABAB" "AB"（前缀AB=后缀AB） 2
4 A "ABABA" "ABA"（前缀ABA=后缀ABA） 3
5 C "ABABAC" 无 0

理解前缀函数的关键在于：π[i] = 3意味着子串pattern[0..2]（即"ABA"）和子串pattern[3..5]（即"ABA"）完全相同。当匹配到位置5失败时，我们可以将模式串的前3个字符（"ABA"）直接与刚刚匹配好的"ABA"对齐，而不需要从头开始比较。

四、前缀函数的计算

前缀函数的计算采用递推方式，从左到右依次求解。假设我们已经知道了π[0], π[1], ..., π[i-1]，现在需要计算π[i]。关键在于利用π[i-1]的值来加速计算过程。

递推构建算法

def compute_pi(pattern): m = len(pattern) pi = [0] * m for i in range(1, m): j = pi[i - 1] while j > 0 and pattern[i] != pattern[j]: j = pi[j - 1] if pattern[i] == pattern[j]: j += 1 pi[i] = j return pi

算法步骤详解

递推构建的核心逻辑可以分解为以下步骤：

  1. 初始化：π[0] = 0，因为单个字符没有真前后缀。
  2. 取前值：令j = π[i-1]，即前一个位置的最长相同前后缀长度。
  3. 尝试扩展：如果pattern[i] == pattern[j]，说明可以在前一个最长前后缀的基础上扩展一位，即π[i] = j + 1。
  4. 回退寻找：如果pattern[i] != pattern[j]，则令j = π[j-1]，回退到更短的相同前后缀，重复检查。这个过程最多进行O(m)次。
  5. 最终赋值：如果最终j回退到0且仍然不相等，则π[i] = 0。

回退的正确性理解：为什么当pattern[i] != pattern[j]时要令j = π[j-1]？因为我们要找的是"pattern[0..i-1]中，既是前缀又是后缀，且其下一个字符等于pattern[i]的最长子串"。π[j-1]恰好是满足"前缀的前缀=后缀的后缀"的最长长度，保证了"同时是pattern[0..i-1]的前缀和后缀"这一性质。这就是KMP算法的精髓所在。

优化版本的前缀函数

在KMP的实际应用中，通常还会对前缀函数进行一步优化：当pattern[i+1] == pattern[π[i]]时，如果匹配到i+1位置失败，跳转到π[i]后还会立即失败，因此可以继续递归回退。优化后的next数组可以进一步减少匹配过程中的无用比较。

def compute_next_optimized(pattern): m = len(pattern) pi = [0] * m nxt = [0] * m for i in range(1, m): j = pi[i - 1] while j > 0 and pattern[i] != pattern[j]: j = pi[j - 1] if pattern[i] == pattern[j]: j += 1 pi[i] = j # 优化：如果下一个字符相同，继续递归 if i + 1 < m and pattern[i + 1] == pattern[j]: nxt[i] = nxt[j - 1] if j > 0 else 0 else: nxt[i] = j return pi, nxt

五、KMP主匹配过程

有了前缀函数（π数组）之后，KMP的主匹配过程就非常清晰了。匹配过程同样使用两个指针：i遍历文本串，j遍历模式串。与朴素匹配最大的不同在于，当匹配失败时，i不回溯，仅通过π数组调整j的位置。

完整KMP匹配实现

def kmp_search(text, pattern): n, m = len(text), len(pattern) if m == 0: return [] pi = compute_pi(pattern) positions = [] j = 0 for i in range(n): while j > 0 and text[i] != pattern[j]: j = pi[j - 1] if text[i] == pattern[j]: j += 1 if j == m: positions.append(i - m + 1) j = pi[j - 1] return positions

匹配过程示例

我们通过一个完整的例子来说明KMP的匹配过程。文本串T = "ABABABAC"，模式串P = "ABABAC"。

步骤 i j T[i] vs P[j] 操作 对齐位置
1 0~4 0~4 全部相等 匹配到j=5 0
2 5 5 T[5]='B' vs P[5]='C' 失败，j=π[4]=3 0
3 5 3 T[5]='B' vs P[3]='B' 相等，j=4 2
4 6 4 T[6]='A' vs P[4]='A' 相等，j=5 2
5 7 5 T[7]='C' vs P[5]='C' 相等，j=6=m 2

可以看到，在位置5匹配失败后，j从5回退到3（因为π[4]=3意味着"ABA"既是前缀也是后缀），然后直接继续比较T[5]和P[3]。文本串指针i从未回退，整个过程只进行了10次字符比较。

KMP的核心优点：在整个匹配过程中，文本串指针i始终向前移动，不会发生回溯。这意味着对于长度为n的文本串，i最多从0走到n-1，匹配阶段的时间复杂度严格为O(n)。这正是KMP能够实现线性时间匹配的根本原因。

六、KMP算法的正确性证明

理解KMP算法的正确性有助于在实际应用中灵活变通。从数学角度，KMP的正确性基于以下两个不变量的证明：

不变量一：前缀函数递推的正确性

假设已知π[0..i-1]全部正确，现在计算π[i]。设j = π[i-1]，即pattern[0..i-1]的最长相同前后缀长度为j。此时我们检查pattern[i]和pattern[j]：如果相等，则显然π[i] = j+1。如果不等，我们需要找下一个候选k < j，使得pattern[0..k-1] = pattern[i-k..i-1]。而这个k正是π[j-1]（因为j是上一个匹配长度，而pattern[0..j-1]的最长相同前后缀π[j-1]会同时是pattern[0..i-1]的前缀和后缀）。通过这样的递推，我们保证能找到最长的那个k。

不变量二：匹配过程的不回溯

当匹配到T[i] != P[j]时，我们已经知道T[i-j..i-1] = P[0..j-1]。设k = π[j-1]，则P[0..k-1] = P[j-k..j-1] = T[i-k..i-1]。因此我们可以将模式串向右移动j-k位，使P[0..k-1]与T[i-k..i-1]对齐，然后从P[k]开始与T[i]比较。这就保证了i不需要回溯，算法始终保持线性时间。

直观理解：可以把KMP想象成一个"聪明的匹配器"，它在每个位置都记住了"如果匹配到这里失败了，我之前已经匹配好的部分中，有多少是不需要重新比较的"。这种记忆能力就是通过π数组实现的。

七、KMP的扩展应用

KMP算法不仅仅是一个字符串匹配算法，其核心思想——前缀函数的计算——在许多其他字符串问题中也有广泛应用。

应用一：查找模式串在文本串中的所有出现

这是KMP最直接的应用。通过在匹配到完整模式串后继续令j = π[j-1]，可以找出所有重叠的出现。正如上面kmp_search函数中所示，当j == m时记录位置后，令j = π[j-1]继续搜索。

应用二：寻找字符串的最小循环节

这是一个非常经典的应用。对于一个长度为m的字符串s，计算其π数组后，最小循环节的长度为m - π[m-1]（前提是m % (m - π[m-1]) == 0，否则字符串没有完整的循环节）。如果π[m-1] > 0且m % (m - π[m-1]) == 0，则s由循环节重复m / (m - π[m-1])次构成。

def min_cycle(s): """返回字符串s的最小循环节长度，若无完整循环节则返回len(s)""" m = len(s) pi = compute_pi(s) cycle = m - pi[-1] if m % cycle == 0: return cycle return m

应用三：字符串的周期判断

字符串的周期T定义为：对于所有0 ≤ i < m-T，有s[i] = s[i+T]。利用π数组可以快速判断：如果π[m-1] > 0，则m - π[m-1]是s的一个周期。进一步地，所有满足(m % (m - π[m-1]) == 0)且(m / (m - π[m-1]))能整除的整数都是s的周期。

def all_periods(s): """返回字符串s的所有周期""" m = len(s) pi = compute_pi(s) periods = [] j = pi[-1] while j > 0: periods.append(m - j) j = pi[j - 1] periods.append(m) return periods

应用四：字符串前后缀匹配问题

给定一个字符串s，求出所有既是s的前缀又是s的后缀的子串长度。这个问题可以通过反复取π[m-1]、π[π[m-1]-1]、...直到0来解决，每条路径上的长度值都是满足条件的解。

def prefix_suffix_lengths(s): """返回所有既是s前缀又是s后缀的子串长度""" m = len(s) pi = compute_pi(s) lengths = [] j = pi[-1] while j > 0: lengths.append(j) j = pi[j - 1] return lengths

应用总结：KMP前缀函数的本质是对字符串"自我重复结构"的刻画。无论是匹配、循环节还是周期判断，本质上都是在利用字符串中前后缀重复的信息来避免重复计算。掌握前缀函数的这一本质，就能灵活地将KMP思想应用到各种字符串问题中。

八、KMP的变体与优化

基于DFA的KMP实现

KMP算法还可以用有限自动机（DFA）的视角来理解。在这种视角下，前缀函数定义了自动机的状态转移：当前状态为j（即已匹配j个字符），读入字符c后，如果c == pattern[j]，则进入状态j+1；否则根据π数组回退状态。这种DFA视角的KMP实现可以使匹配过程更加简洁明了。

class KMPAutomaton: """基于DFA的KMP自动机实现""" def __init__(self, pattern): self.pattern = pattern self.m = len(pattern) self.pi = compute_pi(pattern) def transition(self, state, char): """计算从state状态读入char后的新状态""" while state > 0 and char != self.pattern[state]: state = self.pi[state - 1] if char == self.pattern[state]: state += 1 return state def search(self, text): positions = [] state = 0 for i, ch in enumerate(text): state = self.transition(state, ch) if state == self.m: positions.append(i - self.m + 1) state = self.pi[state - 1] return positions

二维KMP

KMP思想可以扩展到二维模式匹配（在二维网格中匹配一个二维模式）。其思路是对每一行先计算一维KMP的匹配结果，然后在列方向上再应用一次KMP。这种二维KMP在图像处理和计算机视觉中有重要应用。

多模式串的扩展—AC自动机

当需要同时匹配多个模式串时，KMP的思想被扩展为Aho-Corasick自动机（AC自动机）。AC自动机在Trie树上构建失败指针（相当于KMP中π数组的多模式版本），实现了多模式串的线性时间匹配。这是KMP思想在更复杂场景下的重要应用。

AC自动机与KMP的关系：AC自动机可以看作是KMP从单模式串到多模式串的推广。KMP的π数组对应于AC自动机的fail指针，KMP的回退操作对应于AC自动机沿着fail链跳转。理解了KMP，理解AC自动机就会容易很多。

九、实战题目与代码验证

下面通过LeetCode上的一道经典题目来验证KMP算法的实际应用。

LeetCode 28. 实现strStr()

题目要求：实现strStr()函数，给定一个haystack字符串和一个needle字符串，在haystack字符串中找出needle字符串出现的第一个位置（下标从0开始）。如果不存在，则返回-1。

def strStr(haystack, needle): """LeetCode 28 - 使用KMP实现""" if not needle: return 0 n, m = len(haystack), len(needle) # 计算前缀函数 pi = [0] * m for i in range(1, m): j = pi[i - 1] while j > 0 and needle[i] != needle[j]: j = pi[j - 1] if needle[i] == needle[j]: j += 1 pi[i] = j # KMP匹配 j = 0 for i in range(n): while j > 0 and haystack[i] != needle[j]: j = pi[j - 1] if haystack[i] == needle[j]: j += 1 if j == m: return i - m + 1 return -1

LeetCode 459. 重复的子字符串

题目要求：给定一个非空的字符串s，检查它是否可以通过由它的一个子串重复多次构成。

def repeatedSubstringPattern(s): """LeetCode 459 - 使用KMP的π数组判断""" m = len(s) pi = compute_pi(s) cycle = m - pi[-1] return pi[-1] > 0 and m % cycle == 0

LeetCode 214. 最短回文串

题目要求：给定一个字符串s，通过在字符串前面添加字符将其转换为回文串，找到并返回最短的回文串。KMP解法：构造字符串s + '#' + reverse(s)，然后计算其π数组，利用前缀函数找到最长的回文前缀。

def shortestPalindrome(s): """LeetCode 214 - 使用KMP求最短回文串""" rev = s[::-1] combined = s + '#' + rev pi = compute_pi(combined) # pi[-1]是最长的既是combined前缀又是combined后缀的长度 # 即s中最长的回文前缀的长度 longest_pal_prefix = pi[-1] to_add = rev[:len(s) - longest_pal_prefix] return to_add + s

十、KMP的局限性与适用场景

虽然KMP算法是字符串匹配领域的重要里程碑，但它并非在所有场景下都是最优选择。了解其局限性有助于在实践中做出正确的技术选型。

适用场景

局限性

算法选型建议：在实际开发中，Python内置的in操作符和str.find()方法已经高度优化（内部使用了Boyer-Moore和快速搜索的结合），对于绝大多数场景已经足够。KMP更适合于需要自定义匹配逻辑、需要同时获取匹配位置以外的信息（如循环节）、或者在学习算法设计原理的场合使用。

十一、核心要点总结

  • 核心思想：KMP利用已匹配部分的信息，通过前缀函数避免文本串指针回溯，实现O(n+m)的线性时间匹配。
  • 前缀函数π[i]：表示pattern[0..i]的最长相等前后缀长度，是KMP预处理阶段的核心产物。
  • 递推计算：π[i]通过不断回退到π[π[i-1]-1]来递推求解，整个计算过程的时间复杂度为O(m)。
  • 匹配过程：文本串指针i永不回溯，模式串指针j根据π数组灵活跳转，每个字符至多比较两次。
  • 扩展应用：最小循环节（m - π[m-1]）、字符串周期、前缀后缀匹配、AC自动机的基础。
  • 时间复杂度：预处理O(m) + 匹配O(n) = 总时间O(n+m)，空间O(m)。

十二、进一步思考

KMP算法的优美之处在于它将一个看似简单的"字符比较"问题提升到了利用字符串自相似结构的高度。π数组不仅仅是一个"跳转表"，更是对字符串重复模式的数学刻画。这种"从已经完成的工作中提取模式信息来指导未来操作"的思想，在计算机科学的许多领域都有体现，如动态规划中的状态缓存、数据库查询优化中的统计信息利用、机器学习中的特征提取等。

学习建议：理解KMP的最佳方式不是记忆代码，而是手动模拟几次前缀函数的计算过程和匹配过程。拿一支笔和一张纸，选择一个中等长度的模式串（如"ABABAC"），逐步骤地手动计算π数组，然后模拟匹配过程。当你能够准确预测每一步j的跳转位置时，KMP就真正掌握了。

延伸阅读：
- 算法导论（CLRS）第32章：字符串匹配
- AC自动机（Aho-Corasick Algorithm）
- Z算法（Z-Algorithm / Z-function）
- 后缀数组与后缀自动机
- Manacher算法（最长回文子串）