Waymaker 与交叉创新中心联合 Logo
← 返回博客列表

KMP 算法详解：从原理到 Go 语言实现

ryou •

原文地址：https://www.cnblogs.com/ryuo-ou/p/19699021 同步说明：该文已完整同步到站内博客，便于统一检索和阅读。

虽然现在的编程语言标准库（如 Go 的 strings.Index 或 Python 的 find）通常已经提供了极其高效的实现（有时是 Rabin-Karp 或优化过的暴力法），但理解 KMP 仍然是学习算法思维的重要一课。

1. 为什么需要 KMP？

假设我们需要在文本串 haystack 中查找模式串 needle。

暴力解法 (Brute Force) 的思路很简单：
从 haystack 的每一个字符开始，尝试匹配 needle。如果匹配到一半失败了，haystack 的指针 i 就要回溯到上一次起点的下一位，needle 的指针 j 重置为 0。

  • 问题：当我们已经匹配了一长串字符（比如 AAAAAB 中的 AAAAA），一旦失败，暴力法会丢弃所有已知信息。
  • 时间复杂度：最坏情况下是 \(O(N \times M)\)。

KMP 的优化：
当匹配失败时，文本串指针 i 绝不回退。我们只调整模式串指针 j 的位置，利用已经匹配过的信息，跳过那些绝对不可能匹配的位置。

  • 时间复杂度：稳定在 \(O(N + M)\)。

2. 核心概念：Next 数组 (前缀表)

KMP 的核心在于一个辅助数组，通常称为 next 或 pi (prefix function)。

什么是“最长相等前后缀”？

对于模式串的一个子串，我们关注它的前缀和后缀相等的最长长度。

举个例子，模式串 A B A B C：

  • "A": 前后缀无重叠，长度 0
  • "AB": 前缀 A，后缀 B -> 无相等，长度 0
  • "ABA": 前缀 A，后缀 A -> 长度 1
  • "ABAB": 前缀 AB，后缀 AB -> 长度 2
  • "ABABC": 无相等前后缀 -> 长度 0

next[i] 存储的就是 needle[0...i] 这个子串的最长相等前后缀长度。

这个数组有什么用？

当我们在 j 处匹配失败时，说明 needle[0...j-1] 这部分是匹配成功的。
我们可以查表看 next[j-1] 是多少。假设是 2，通过前缀性质，我们知道模式串开头的 2 个字符一定可以匹配上文本串刚刚经过的 2 个字符。
于是，我们可以直接把 j 移动到 2，而不需要移动 i。

3. Go 语言代码实现

下面是标准的 KMP 实现。逻辑分为两部分：构建 next 数组和主匹配循环。

func strStr(haystack string, needle string) int { n, m := len(haystack), len(needle) if m == 0 { return 0 } // ----------------------------------- // 第一步：构建 next 数组 (前缀表) // ----------------------------------- // next[i] 表示 needle[0...i] 的最长相等前后缀长度 next := make([]int, m) // i 指向后缀末尾，j 指向前缀末尾 // j 同时也代表了当前最长相等前后缀的长度 for i, j := 1, 0; i < m; i++ { // 关键点：如果不匹配，j 不断回退 // 回退到 next[j-1]，也就是看前缩短一点的前缀能不能匹配 for j > 0 && needle[i] != needle[j] { j = next[j-1] } // 如果匹配，j 长度加 1 if needle[i] == needle[j] { j++ } // 记录当前位置 i 的 next 值 next[i] = j } // ----------------------------------- // 第二步：主匹配循环 // ----------------------------------- // 逻辑和构建 next 数组几乎完全一致 for i, j := 0, 0; i < n; i++ { // 如果文本串和模式串不匹配 // j 根据 next 数组回退，i 保持不动（不回溯） for j > 0 && haystack[i] != needle[j] { j = next[j-1] } // 如果匹配成功，j 向前走 if haystack[i] == needle[j] { j++ } // j 走到了模式串末尾，说明完全匹配 if j == m { return i - m + 1 } } return -1
}

4. 图解匹配过程（简化版）

假设：
文本串(S): A B A B A B C
模式串(P): A B A B C

  1. i=0, 1, 2, 3: S[i] == P[j] 一路匹配。
  2. i=4 (A) vs j=4 (C):
    • 此时 S[4] 是 'A'，P[4] 是 'C'。不匹配！
    • 此时 j=4，我们查看 next[j-1] 即 next[3]。
    • P[0...3] 是 "ABAB"，最长相等前后缀是 "AB"，长度为 2。
    • 操作：j 变为 2。这意味着我们可以认为前两个字符 P[0...1] ("AB") 已经匹配上了（因为后缀 "AB" 匹配了，而前缀 "AB" 等于后缀 "AB"）。
  3. i=4 (A) vs j=2 (A):
    • 此时 P[2] 是 'A'。匹配！
    • j 增加变为 3。
  4. i=5 (B) vs j=3 (B): 匹配。
  5. i=6 (C) vs j=4 (C): 匹配。j 到达末尾，返回结果。

5. 复杂度分析

  • 时间复杂度: \(O(N + M)\)
    • 构建 Next 数组需要 \(O(M)\)。
    • 主循环虽然有 while 回退，但 i 是一直前进的，j 最多增加 \(N\) 次，也就最多减少 \(N\) 次。摊还分析后是 \(O(N)\)。
  • 空间复杂度: \(O(M)\)
    • 需要一个长度为 \(M\) 的 next 数组。

6. 总结

KMP 看起来复杂，其实诀窍就在于利用已知的匹配信息。
记住核心代码模板：

  1. for 循环遍历主串指针 i。
  2. while 循环处理不匹配情况，利用 next 数组回退 j。
  3. if 判断单字符匹配更新 j。
← 返回首页