深入理解 KMP 字符串匹配算法 – wiki基地

作者： /

深入理解 KMP 字符串匹配算法

引言：字符串匹配的基石

在计算机科学的广阔领域中，字符串匹配是一个基础且至关重要的问题。无论是在文本编辑器中搜索特定词语、在基因序列中寻找特定模式、在网络流量中检测恶意代码，还是在数据库中执行查询，字符串匹配算法都扮演着核心角色。其基本任务是：给定一个主文本字符串（Text）和一个模式字符串（Pattern），判断模式串是否在主串中出现，如果出现，则找出其所有出现的位置。

最直观、最容易想到的方法是朴素（Brute-Force）字符串匹配算法。然而，正如我们将在下面探讨的，朴素算法在某些情况下效率低下。为了克服这些限制，计算机科学家们开发了更高效的算法，其中 Knuth-Morris-Pratt（KMP）算法以其精妙的设计和线性时间复杂度而闻名遐迩。本文旨在深入探讨 KMP 算法的原理、实现细节及其优势，帮助读者全面理解这一经典的字符串匹配技术。

一、朴素字符串匹配算法及其瓶颈

在深入 KMP 之前，我们有必要先理解朴素算法的工作方式及其存在的问题。

朴素算法思想：
朴素算法的思路非常直接：

  1. 将模式串 P 的首字符与主串 T 的首字符对齐。
  2. 从左到右逐一比较 P 和 T 中对应位置的字符。
  3. 如果 P 中的所有字符都与 T 中的对应字符匹配成功，则找到了一个匹配，记录下起始位置。
  4. 如果比较过程中遇到不匹配的字符，或者 P 已经匹配完，则将 P 相对于 T 向右移动一位。
  5. 重复步骤 2-4，直到 T 的末尾（或者说，直到 P 的起始位置超过了 T 中可能匹配的最后一个位置）。

示例：
假设 主串 T = “ABCABABCA”，模式串 P = “ABABC”

  1. ABCABABCA
    ABABC (匹配到 C vs B 时失败)
  2. ABCABABCA
    ABABC (匹配到 C vs A 时失败)
  3. ABCABABCA
    ABABC (匹配成功！) 记录起始位置 2 (0-indexed)
  4. ABCABABCA
    ABABC (匹配到 A vs C 时失败)
  5. … 以此类推

瓶颈分析：
朴素算法在大多数情况下工作良好，但考虑一种极端情况：
T = “AAAAAAAAAAAAAAAAAB”
P = “AAAAAB”

当 P 与 T 的前缀对齐时，前 5 个 ‘A’ 都能匹配，直到第 6 个字符 (‘B’ vs ‘A’) 发生不匹配。此时，朴素算法会将 P 右移一位：

T: AAAAAAAAAAAAAAAAAB
P: AAAAA B (仍然不匹配)

接着再右移一位，直到 P 的 ‘B’ 对齐 T 的 ‘B’ 才可能成功。在这个过程中，主串 T 中的字符被反复比较。例如，T[1] 在 P 向右移动时，会被 P[0] 比较多次。主串的指针在每次匹配失败后都需要回溯（虽然实现上通常是模式串右移，等效于主串指针的回溯），导致了大量冗余的比较操作。

在最坏情况下（例如 T 全是 ‘A’，P 是多个 ‘A’ 后跟一个 ‘B’），每次 P 的移动都几乎要比较完整个 P 的长度，其时间复杂度会达到 O(n * m)，其中 n 是主串 T 的长度，m 是模式串 P 的长度。对于长文本和长模式串，这种效率是难以接受的。

二、KMP 算法的核心思想：避免冗余比较

KMP 算法的精髓在于，它认识到在匹配失败时，我们并非一无所知。已经比较过的那部分字符（即匹配失败位置之前的 P 的前缀）蕴含着有用的信息，可以帮助我们决定下一次应该将模式串 P 向右移动多少位，而不是仅仅移动一位。关键在于，KMP 算法通过预处理模式串 P，构建一个辅助数组（通常称为 next 数组或 lps 数组），使得在匹配过程中，主串 T 的指针永不回溯，只向前移动。

核心洞察：
假设在主串 T 的 i 位置和模式串 P 的 j 位置发生不匹配（即 T[i] != P[j]）。这意味着在不匹配发生之前，主串中从 i-j 到 i-1 的子串与模式串中从 0 到 j-1 的子串是完全匹配的。即 T[i-j ... i-1] == P[0 ... j-1]。

此时，我们不想简单地将 P 右移一位再从头比较。我们希望找到 P 的一个真前缀（Proper Prefix，即不等于 P 自身的前缀），使得这个真前缀同时也是 P[0 ... j-1] 的一个后缀，并且这个真前缀尽可能的长。

为什么？假设 P[0 ... k-1] 是 P[0 ... j-1] 的最长公共前后缀（即最长的、既是 P[0 ... j-1] 的真前缀又是其后缀的子串），长度为 k。
这意味着 P[0 ... k-1] == P[j-k ... j-1]。

由于我们已知 T[i-j ... i-1] == P[0 ... j-1]，那么必然有 T[i-k ... i-1] == P[j-k ... j-1]。
结合上面两个等式，可得 T[i-k ... i-1] == P[0 ... k-1]。

这告诉我们什么？当我们把模式串 P 向右移动 j - k 位时，P 的前 k 个字符 P[0 ... k-1] 必然已经与主串 T 中紧邻 i 位置之前的 k 个字符 T[i-k ... i-1] 匹配上了！

因此，在 T[i] 和 P[j] 失配后，我们不需要从 P 的开头重新比较，可以直接从 P 的第 k 个字符（P[k]）开始，与主串 T 的 i 位置字符（T[i]）进行比较。模式串 P 的指针 j 直接跳转到 k。

这就是 KMP 算法避免主串指针回溯、提高效率的关键：利用已匹配前缀的结构信息，计算出模式串 P 在失配时可以“安全”地向右滑动的最大距离。

三、next 数组（前缀函数）的构建

为了实现上述的“智能滑动”，我们需要预先计算出模式串 P 的所有前缀的最长公共前后缀长度。这个信息通常存储在一个称为 next 的数组中（有时也叫 lps 或 pi）。

定义：
next[j] 存储的是模式串 P 的子串 P[0 ... j] 的最长相等前后缀（Longest Proper Prefix which is also Suffix, LPS）的长度。这里的“真前缀”意味着前缀不能是字符串本身。

注意： next 数组的定义有多种细微差别，有时 next[j] 存储的是 P[0...j-1] 的最长公共前后缀长度。我们这里采用常见的定义：next[j] 对应子串 P[0...j]。并且，为了方便 KMP 匹配过程中的使用，有时会将 next 数组整体右移一位并在开头补 -1 或 0，或者在计算逻辑中稍作调整。我们这里先关注其核心含义：计算 P[0...j] 的 LPS 长度。

示例：计算 P = “abababca” 的 next 数组

  • j = 0: P[0] = "a". 真前缀和后缀都为空。next[0] = 0。
  • j = 1: P[0...1] = "ab". 真前缀 {"a"}, 后缀 {"b"}。无公共部分。next[1] = 0。
  • j = 2: P[0...2] = "aba". 真前缀 {"a", "ab"}, 后缀 {"a", "ba"}。最长公共部分是 “a”，长度 1。next[2] = 1。
  • j = 3: P[0...3] = "abab". 真前缀 {"a", "ab", "aba"}, 后缀 {"b", "ab", "bab"}。最长公共部分是 “ab”，长度 2。next[3] = 2。
  • j = 4: P[0...4] = "ababa". 真前缀 {"a", "ab", "aba", "abab"}, 后缀 {"a", "ba", "aba", "baba"}。最长公共部分是 “aba”，长度 3。next[4] = 3。
  • j = 5: P[0...5] = "ababab". 真前缀 {"a", ..., "ababa"}, 后缀 {"b", ..., "babab"}。最长公共部分是 “abab”，长度 4。next[5] = 4。
  • j = 6: P[0...6] = "abababc". 真前缀 {"a", ..., "ababab"}, 后缀 {"c", "bc", ..., "bababc"}。无公共部分。next[6] = 0。
  • j = 7: P[0...7] = "abababca". 真前缀 {"a", ..., "abababc"}, 后缀 {"a", "ca", ..., "bababca"}。最长公共部分是 “a”，长度 1。next[7] = 1。

所以，对于 P = “abababca”，next 数组为 [0, 0, 1, 2, 3, 4, 0, 1]。

计算 next 数组的算法（优化方法）：
我们可以使用动态规划的思想，在 O(m) 时间内计算出 next 数组。计算 next[j] 时，可以利用已计算出的 next[0 ... j-1] 的值。

设 k = next[j-1]。这表示 P[0 ... k-1] 是 P[0 ... j-1] 的最长公共前后缀。
我们现在要比较 P[j] 和 P[k]。

  1. 如果 P[j] == P[k]:
    这太棒了！这意味着 P[0 ... k] 就是 P[0 ... j] 的最长公共前后缀。因为 P[0...k-1] == P[j-k...j-1]，现在 P[k] == P[j]，所以 P[0...k] == P[j-k...j]。因此，next[j] = k + 1。

  2. 如果 P[j] != P[k]:
    这意味着 P[0 ... k] 不能构成 P[0 ... j] 的后缀。我们需要寻找 P[0 ... j-1] 的 次长 的公共前后缀。这个次长的前后缀在哪里找？
    根据 next 数组的定义，P[0 ... k-1] (长度为 k) 的最长公共前后缀的长度是 next[k-1]。
    所以，我们令 k = next[k-1]，得到一个新的、更短的候选前缀 P[0 ... k-1]。
    我们再次比较 P[j] 和 P[k]。
    重复这个过程，不断通过 k = next[k-1] 来缩短候选前缀的长度 k，直到找到一个 k 使得 P[j] == P[k]（此时 next[j] = k + 1），或者 k 缩减到 0。
    如果 k 缩减到 0，我们比较 P[j] 和 P[0]。如果它们相等，next[j] = 1；如果不等，next[j] = 0。

伪代码 (计算 next 数组):

“`python
function compute_next(pattern):
m = len(pattern)
next_array = [0] * m
length = 0 # length of the previous longest prefix suffix
i = 1

while i < m:
if pattern[i] == pattern[length]:
length += 1
next_array[i] = length
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step below.
if length != 0:
# 回溯 k 的值
length = next_array[length – 1]
# Also, note that we do not increment i here
else:
next_array[i] = 0
i += 1
return next_array
“`

这个计算 next 数组的过程本身也类似 KMP 匹配，它在模式串内部进行“自我匹配”。通过分析可以证明其时间复杂度为 O(m)。

四、KMP 匹配过程

有了 next 数组之后，KMP 的匹配过程就变得非常高效：

  1. 初始化两个指针：i = 0 指向主串 T 的当前比较位置，j = 0 指向模式串 P 的当前比较位置。
  2. 循环比较 T[i] 和 P[j]：
    • 如果 T[i] == P[j]: 说明当前字符匹配成功，将两个指针都向前移动一位，即 i++, j++。
    • 如果 T[i] != P[j]: 发生失配。此时需要利用 next 数组来调整模式串 P 的位置。
      • 如果 j != 0: 说明不是在 P 的第一个字符就失配。我们将 P 的指针 j 回溯到 next[j-1] 的位置。即 j = next[j-1]。注意：此时主串 T 的指针 i 保持不变！ 这是 KMP 算法的关键，避免了 T 的回溯。然后继续比较新的 T[i] 和 P[j]。
      • 如果 j == 0: 说明 P 的第一个字符就与 T 的当前字符不匹配。此时无法再利用 P 的前缀信息，只能将 P 整体右移一位。在实现上，这等同于只将主串 T 的指针向前移动一位，即 i++，而 j 保持为 0。
  3. 循环终止条件：
    • 如果 j == m (m 是 P 的长度): 说明 P 中的所有字符都已成功匹配，找到了一个匹配项。记录下匹配的起始位置 i - j。为了查找所有匹配项，此时不能停止。需要像处理失配一样，利用 next 数组来继续查找下一个可能的匹配。令 j = next[j-1]，然后继续比较。
    • 如果 i == n (n 是 T 的长度): 说明主串 T 已经扫描完毕，匹配过程结束。

示例：T = “ABABDABACDABABCABAB”, P = “ABABC”, next = [0, 0, 1, 2, 0] (对应 P[0..j])

（为了方便，我们使用 next 数组的一个变体，令 next[j] 表示 P[0...j-1] 的LPS长度，并在开头加-1，即 next_prime = [-1, 0, 0, 1, 2]。匹配时，失配后 j = next_prime[j]。或者使用上面计算的 next = [0, 0, 1, 2, 0]，失配后 j = next[j-1]。这里我们用后者。）

“`
T: A B A B D A B A C D A B A B C A B A B
P: A B A B C
i=0, j=0: T[0]==P[0] (‘A’==’A’), i=1, j=1
i=1, j=1: T[1]==P[1] (‘B’==’B’), i=2, j=2
i=2, j=2: T[2]==P[2] (‘A’==’A’), i=3, j=3
i=3, j=3: T[3]==P[3] (‘B’==’B’), i=4, j=4
i=4, j=4: T[4]!=P[4] (‘D’!=’C’), 发生失配!
j=4 != 0. 回溯 j: j = next[j-1] = next[3] = 2. i 保持为 4.
P 现在相当于右移了 j – next[j-1] = 4 – 2 = 2 位。
新的 P 对齐:
T: A B A B D A B A C D A B A B C A B A B
P: A B A B C
比较 T[i=4] 和 P[j=2]

i=4, j=2: T[4]!=P[2] (‘D’!=’A’), 发生失配!
j=2 != 0. 回溯 j: j = next[j-1] = next[1] = 0. i 保持为 4.
P 现在相当于右移了 j – next[j-1] = 2 – 0 = 2 位。
新的 P 对齐:
T: A B A B D A B A C D A B A B C A B A B
P: A B A B C
比较 T[i=4] 和 P[j=0]

i=4, j=0: T[4]!=P[0] (‘D’!=’A’), 发生失配!
j=0 == 0. 主串指针前进: i = 5. j 保持为 0.
P 整体右移一位。
新的 P 对齐:
T: A B A B D A B A C D A B A B C A B A B
P: A B A B C
比较 T[i=5] 和 P[j=0]

i=5, j=0: T[5]==P[0] (‘A’==’A’), i=6, j=1
i=6, j=1: T[6]==P[1] (‘B’==’B’), i=7, j=2
i=7, j=2: T[7]==P[2] (‘A’==’A’), i=8, j=3
i=8, j=3: T[8]!=P[3] (‘C’!=’B’), 发生失配!
j=3 != 0. 回溯 j: j = next[j-1] = next[2] = 1. i 保持为 8.
P 右移 j – next[j-1] = 3 – 1 = 2 位.
比较 T[i=8] 和 P[j=1]

… 以此类推，直到找到匹配或 T 扫描完毕。

(最终会在 T[10] 处开始找到匹配 “ABABC”)
i=10, j=0: T[10]==P[0] (‘A’==’A’), i=11, j=1
i=11, j=1: T[11]==P[1] (‘B’==’B’), i=12, j=2
i=12, j=2: T[12]==P[2] (‘A’==’A’), i=13, j=3
i=13, j=3: T[13]==P[3] (‘B’==’B’), i=14, j=4
i=14, j=4: T[14]==P[4] (‘C’==’C’), i=15, j=5
j == 5 (P 的长度). 找到匹配! 起始位置 i – j = 15 – 5 = 10.
继续查找: j = next[j-1] = next[4] = 3. i 保持 15.
比较 T[i=15] 和 P[j=3]
…
“`

伪代码 (KMP 匹配):

“`python
function kmp_search(text, pattern):
n = len(text)
m = len(pattern)
next_array = compute_next(pattern) # 使用上面定义的 next 数组
i = 0 # pointer for text
j = 0 # pointer for pattern
results = []

while i < n:
if pattern[j] == text[i]:
i += 1
j += 1

if j == m:
  # Found a match
  results.append(i - j)
  # Continue searching for more matches
  # Move j using the next array property for pattern[0...m-1]
  j = next_array[j - 1] 
elif i < n and pattern[j] != text[i]:
  # Mismatch after j matches
  # Do not match next_array[0..next_array[j-1]] characters,
  # they will match anyway
  if j != 0:
    j = next_array[j - 1]
  else:
    # If j is 0, just move the text pointer
    i += 1

return results
“`

五、复杂度分析

  • 预处理阶段（计算 next 数组）： 时间复杂度为 O(m)，空间复杂度为 O(m) 用于存储 next 数组。
  • 匹配阶段： 在匹配过程中，主串指针 i 始终单调递增，最多增加 n 次。模式串指针 j 虽然会回溯，但每次回溯（j = next[j-1]）都意味着 P 向右有效滑动。分析 i 的增加和 j 的回溯操作的总次数可知，比较操作的总次数是线性的。具体来说，i 最多增加 n 次。j 的增加总次数也小于 n 次（因为每次 j 增加都伴随 i 增加）。j 的回溯操作 j = next[j-1]，每次回溯都会减小 j 的值，而 j 的总增加量小于 n，所以 j 的总回溯量也小于 n。因此，匹配阶段的时间复杂度是 O(n)。

总体复杂度： KMP 算法的总时间复杂度为 O(n + m)，空间复杂度为 O(m)。这比朴素算法的 O(n * m) 有了显著的提升，特别是当 m 较大或者模式串 P 具有很多重复子结构时。

六、KMP 算法的优势与应用

优势：

  1. 高效性： 线性时间复杂度 O(n+m) 使得它在处理大规模文本和模式串时非常高效。
  2. 避免回溯： 主串指针永不回溯，减少了冗余比较。
  3. 信息利用： 充分利用了模式串本身的结构信息（通过 next 数组）。

缺点：

  1. 理解与实现稍复杂： 相较于朴素算法，next 数组的计算和 KMP 匹配逻辑需要更深入的理解。
  2. 需要额外空间： 需要 O(m) 的额外空间存储 next 数组。
  3. 对于随机性强的短字符串，优势不明显： 如果模式串非常短，或者文本和模式串几乎没有重复结构，预处理的开销可能使得 KMP 相较于朴素算法的优势减弱（但复杂度级别仍更优）。

应用场景：

KMP 算法及其思想被广泛应用于各种需要高效字符串匹配的场景：

  • 文本编辑器和IDE： 文件内查找、代码搜索。
  • 搜索引擎： 网页内容中的关键词匹配。
  • 生物信息学： DNA、蛋白质序列的模式查找与比对。
  • 网络安全： 入侵检测系统（IDS）中匹配已知的攻击签名。
  • 数据压缩： 查找重复的字符串模式。
  • 自然语言处理： 词语查找、模式识别。

七、总结

KMP 算法是字符串匹配领域的一个里程碑式的成就。它通过巧妙地预处理模式串，构建 next 数组来记录模式串前缀的结构信息，从而在匹配过程中避免了主串指针的回溯，实现了 O(n+m) 的线性时间复杂度。理解 KMP 的核心在于理解 next 数组的含义以及它如何在发生失配时指导模式串进行最大程度的安全滑动。尽管其实现比朴素算法复杂，但其效率优势使其在众多实际应用中不可或缺。掌握 KMP 算法不仅能解决具体的字符串匹配问题，更能体会到算法设计中利用问题本身结构信息来优化计算过程的精妙思想。

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部