一文搞懂 KMP 算法：从 next 数组逐步推导到工程应用，拒绝死记硬背

字符串匹配是文本编辑器搜索、日志过滤、入侵检测这些功能的底层能力：在一段长文本里找一个模式串的所有出现位置。这个领域最著名的算法是 KMP——三个发明人姓名的首字母，也是最常被「背错」的算法：next 数组的定义版本五花八门（有的整体右移一位、有的把 next[0] 设为 -1），网上抄来的代码经常拼不出一个能自洽运行的版本；更多人能默写出代码，却解释不清「失配后为什么跳到那个位置是对的」。

这篇文章不打算让你背任何东西。我们从暴力匹配到底浪费在哪一步出发，把 next 数组的含义、构建、使用一步步推出来，最后聊聊它在工程里的真实定位——包括为什么很多文本编辑器用的其实不是 KMP。

问题背景：暴力匹配浪费在哪里

任务定义：主串长 n，模式串长 m，找 pattern 在 text 中的位置。暴力做法很直白：从主串每个起点开始，逐位与模式串比较；失配后起点右移一位，比较指针回到模式串开头重来。正确性没有任何问题，最坏 O(nm)——主串 AAAA...A、模式串 AAAB 时，每个起点都要比到模式串最后一个字符才发现失配，n 起点乘 m 位，乘法级代价。

真正的问题在于：失配前已经匹配成功的那部分信息被完全丢掉了。比如主串 ABABABC、模式串 ABABC，从下标 0 出发比到第五个字符才失配——此时你已经知道主串前五个字符是 ABABA，这个信息足够推出「下一个有效起点至少在哪」，但暴力法视而不见，老老实实从下标 1 的 B 开始重新比。KMP 的全部工作，就是把这白白丢弃的信息捡回来。

思路推导：next 数组为什么是对的

先建立一个关键观察：失配发生时，已经匹配的部分恰好是模式串自己的一个前缀。上面例子里失配前匹配到的是 ABABA，它正是模式串 ABABC 的前缀。也就是说，「接下来模式串该怎么挪」这个问题，与主串内容无关，只取决于模式串自己——完全可以对模式串「自己和自己比」，预先算出每个位置失配后的转移目标。这就是 next 数组（学术界叫前缀函数 π）。

正式定义：next[i] 等于子串 pattern[0..i] 的最长相等真前后缀的长度。「真」的意思是不能是整个子串本身。拿模式串 ABABC 逐位算：next[0] = 0（单字符没有真前后缀）；next[1]，前缀 AB 与后缀……相等的只有长度 0；next[2]，ABA 的前缀 A 等于后缀 A，得 1；next[3]，ABAB 的前缀 AB 等于后缀 AB，得 2；next[4]，ABABC 无相等真前后缀，得 0。于是 next = [0, 0, 1, 2, 0]。

它怎么用？假设匹配进行到模式串第 j 位失配（主串指针停在 i 不动）。已匹配的 pattern[0..j-1] 里，前 next[j-1] 个字符与它的后 next[j-1] 个字符完全相同——而后者就躺在主串 i 的左边。所以模式串滑到 next[j-1] 位继续比较即可：重叠部分的比较天然成立，不用再比。整个过程主串指针 i 永不回退，只增不减——这正是复杂度能线性化的根本原因。

构建 next 数组本身也用同样的逻辑，即「模式串作为主串、模式串作为模式」的自匹配：i 从 1 起扫描，j 记录当前已匹配的前缀长度；失配时 j 退到 next[j-1]，匹配时 j 前进一位并记入 next[i]。构建循环里那两行「退与进」，就是匹配主流程的翻版——理解了匹配，构建自动理解。

实操代码：Python 实现与均摊复杂度证明

def build_next(pattern: str) -> list[int]:
    """构建前缀函数：next[i] = pattern[0..i] 最长相等真前后缀的长度"""
    m = len(pattern)
    nxt = [0] * m
    j = 0                              # j：当前已匹配的前缀长度
    for i in range(1, m):              # i 从 1 起，next[0] 恒为 0
        while j > 0 and pattern[i] != pattern[j]:
            j = nxt[j - 1]             # 失配：退到上一个最长相等前后缀
        if pattern[i] == pattern[j]:
            j += 1                     # 匹配：前缀延长一位
        nxt[i] = j
    return nxt


def kmp_search(text: str, pattern: str) -> int:
    """返回 pattern 在 text 中首次出现的下标，未找到返回 -1"""
    if not pattern:
        return 0                       # 空模式约定命中下标 0
    if len(pattern) > len(text):
        return -1
    nxt = build_next(pattern)
    j = 0                              # j：已匹配的模式串长度
    for i, ch in enumerate(text):
        while j > 0 and ch != pattern[j]:
            j = nxt[j - 1]             # 模式串回退，主串指针 i 永不回退
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):          # 完整匹配成功
            return i - j + 1
    return -1


if __name__ == "__main__":
    print(build_next("ABABC"))         # [0, 0, 1, 2, 0]
    print(kmp_search("ABABABCABAB", "ABABC"))   # 2

复杂度证明的关键在 while 循环：它在整个运行期执行的总回退次数，不可能超过 j 的总增长次数——j 每次回退至少减一，而 j 只在字符匹配成功时加一，全程至多加 n 次，所以回退总次数至多 n。于是每轮均摊 O(1)，构建 O(m)、匹配 O(n)，总计 O(n + m)，且这是最坏情况保证，不是平均情况。边界条件：空模式按惯例返回 0；模式比主串长直接返回 -1；while 的前置条件 j > 0 保证 next[j-1] 不会越界。

工程应用上，KMP 的 next 数组还是一把「周期检测」的钥匙：设 next[m-1] = L，若 m % (m - L) == 0，则整个串由长度为 m - L 的子串循环构成（例如 ababab 的 next = [0,0,1,2,3,4]，m - L = 2，2 整除 6，周期为 2）。把主流程里「匹配成功即返回」改成「记录起点后 j = nxt[j-1] 继续」，就能找出所有出现位置并天然支持重叠匹配。至于定位：纯文本搜索场景里 Boyer-Moore（坏字符启发，主流编辑器采用）和 Sunday 往往更快，因为自然语言的字符集大、启发式跳跃激进；KMP 的不可替代性在于最坏情况线性保证与流式匹配（无需预读主串后续内容），DNA 序列这类小字符集、坏情况概率现实的场景尤其合适。选型前先想清楚你要的是平均快还是保证不慢。

避坑总结

1. next 数组定义不统一，跨语言抄码必错。有的教材整体右移一位、有的 next[0] = -1，同一个词三种含义。动手前先写清自己的定义（本文用前缀函数版），再检查参考代码是否同一定义。
2. 主串指针一旦出现回退，基本就是写回了暴力法。「i 永不回退」是线性复杂度的命根子，review 自己的 KMP 实现时先盯这一条。
3. 构建循环里 while 必须在 if 之前，且带 j > 0 前置条件。顺序颠倒或漏掉前置条件，next[j-1] 直接数组越界。
4. 查找所有出现位置时，匹配成功后必须 j = nxt[j-1] 而不是 j = 0。清零会漏掉跨界重叠的匹配，比如在 aaaa 里找 aa 应命中 3 次，清零版只能找到 2 次。
5. 周期判定公式别背错下标。用 next[m-1]（整串的最长相等前后缀），下标写成 m 或 m+1 是常见笔误；判周期前先确认 next 数组定义与公式配套。

写在最后

KMP 教给我们的远不止一个匹配算法，而是一种思维方式：当一次失败发生了，别急着从头再来，先盘一盘这次失败已经攒下了哪些信息。next 数组就是「已匹配信息」的静态账本——用模式串自匹配一次，把每个位置失败后的最优转移全部预结算好。带着这个视角，再去理解 AC 自动机（KMP 的多模式推广）、后缀数组等更复杂的结构，会发现它们做的仍是同一件事：让已经付出的比较成本不被浪费第二次。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。