KMP字符串匹配算法：next数组的登山保护点

可视化演示

KMP算法通过next数组实现O(n+m)线性时间字符串匹配，避免了朴素算法的回溯。本文讲解KMP算法的暴力匹... 切换模式查看不同维度。

朴素匹配之痛：没有岩钉的登山者

一个没有岩钉、不做任何记录的登山者，会如何寻找与路线图吻合的岩壁？他会从山脚第一个位置开始，照图往上爬；一旦某一步对不上，就滑回山脚，从第二个位置重新攀爬。这种“暴力攀登”在直觉上很简单，却隐藏着巨大的体力浪费——每次滑落都丢弃了之前所有验证过的安全高度。

这个场景对应字符串匹配中的朴素算法：主串从第 0 位到第 n-m 位逐一作为起点，把模式串 m 个字符从头逐个比较。每次失配后，主串指针回到“当前起点 + 1”，模式串指针归零。表面上每个起点最多比较 m 次，但最坏情况下，比如主串为 AAAAAAB、模式串为 AAAAB，每个起点都要辛辛苦苦爬到第 4 步才惊觉失配，再跌落回山脚。

登山者很快意识到：每次回到山脚重新爬，意味着同一个位置反复被踩踏，体力的浪费全在“重复”。既然已经爬到过某个高度，为什么不能在那个高度挂上一颗岩钉，下次失手时只退到那里？这正是公共前后缀要解决的第一个问题。

公共前后缀：岩壁上的重复纹路

聪明的登山者在攀爬中注意到一个现象：岩壁的纹路常常有规律。沿着已爬过的这一段，某些后缀的形状恰好与这条路线图开头的某个前缀一模一样。如果能记住“这一段的前后端有多长是重复的”，那么失手时就可以退到那个位置继续，而不是退到山脚。

对模式串 P 而言，前 i 个字符（下标 0 到 i-1）的最长公共前后缀，记作 π[i]：它既等于这 i 个字符开头的一段前缀，又等于同样长度、以第 i-1 个字符结尾的一段后缀，且长度尽量大。例如模式串 ABABCAB 中，前 7 个字符自己的前缀 AB 和后缀 AB 相同，所以 π[7]=2。

对 ABABCAB 手工演算：前 1 个字符 A 的 π=0；前 2 个 AB 的 π=0；前 3 个 ABA 的 π=1（前缀 A=后缀 A）；前 4 个 ABAB 的 π=2（AB=AB）；前 5 个 ABABC 的 π=0；前 6 个 ABABCA 的 π=1；前 7 个 ABABCAB 的 π=2。这张“纹路重复表”正是岩钉表的前身——现在要解决的是：怎样边爬边把岩钉钉进去。

next数组构建：边攀爬边钉岩钉

登山者不希望在出发前花大量时间研究整条路线，他更想边爬边钉：每走一步，只需要回顾“刚刚走完的这一段和开头哪一段相同”，就能确定新的岩钉位置。这正是 next 数组的递推构建思想——不需要回头反复扫描，一个指针 i 负责爬山，一个指针 j 负责比对“当前已匹配前缀有多长”。

初始时约定 next[0] = -1，这是“山脚哨兵”：当模式串第一个字符就失配时，表示无路可退，登山者必须把主线（主串）向前推一步。随后，让模式串自己和自己比较：若 P[i] == P[j]，说明公共前后缀延长了一格，于是 next[i+1] = j + 1，两个指针一起前进；若不相等，j 则沿着已有的 next 链回退，直到 j=-1 或找到相等字符。

以 ABABCABAB 为例推演，最终得到 next = [-1, 0, 0, 1, 2, 0, 1, 2, 3]。登山者手里的岩钉表就这样在攀爬中完成了。值得注意的是，即使卡在某一步需要沿 next 链回退多次，回退的总次数也极为有限——这正是下一节匹配心法和第六节复杂度分析的基石。

匹配过程心法：失手只滑到最近岩钉

带着岩钉表的登山者终于正式上场了。他的铁律只有一条：主线路（主串指针 i）绝不后退，失手时只利用岩钉表把模式串指针 j 拉到安全位置。第 j 位失配时，前 j 个字符已经和主串完全吻合，而这些字符的最长公共前后缀长度正好是 next[j]——那意味着主串的当前位置之前，有一段已知安全的路可以复用。

于是匹配过程变得极简：字符相等，i++、j++；字符不等，i 原地不动，j = next[j]；当 next[j] = -1 时，登山者知道脚下根本没有岩钉可借力，只能让 i++ 且 j=0。这个过程中，主串的每个字符最多被“看一眼”就永远不会回头看，模式串则反复借用岩钉缩短回退距离。

对照可视化演示可以清楚地看到：当主串第 6 位 D 与模式串第 4 位 C 失配时，i 停在原处，j 从 4 跳到 next[4]=2，继而比对 A。这次跳转让登山者保留了已确认的 AB 两个高度，避免了从山脚重爬。可是，新的问题出现了：如果岩钉的位置上是一块光滑的“重复石板”，跳过去是否还是会滑落？

nextval优化：拔出打滑的岩钉

登山者在使用岩钉表时发现了一个尴尬情况：有些岩钉钉上去根本没有意义。例如模式串 AAAA，若第 4 个 A 失配，next[4]=3 会让他退到第 3 个 A 继续比——但主串那个字符既然和第 4 个 A 不等，就一定和第 3 个 A 也不等。跳过去等于注定再失败一次，白费一段手脚。

nextval 就是“拔出打滑岩钉”的手术：在构建 next 之后，再检查每一位。若 P[j] == P[next[j]]，说明跳转目标是同一个字符，跳了也白跳，干脆直接继承 nextval[next[j]]；只有 P[j] != P[next[j]] 时，next[j] 本身才值得保留。这样就把“必然再次失配”的跳转压缩掉了。

以 AAAA 为例：next = [-1, 0, 1, 2]，修正后 nextval = [-1, -1, -1, -1]。登山者发现整面墙都是同一种石板，最安全的做法是失配时直接滑落回山脚哨兵，连中间那几步重复的试探都省去。nextval 并不改变算法框架，它只是让每一颗岩钉都真正“挂得住”。

复杂度分析：线性收益背后的账本

现在来算一笔登山者的体力账。整条主线路（主串）从第 0 米延伸到第 n-1 米，主串指针 i 在匹配过程中只增不减，最多走 n 步。模式串指针 j 的每次增长，都来源于一次成功的字符匹配，而成功的匹配总数不可能超过主串长度 n。失配时 j 回退到 next[j]，每跳一次至少变小一点，可回退的“总高度”被 j 的增长总量所限制。

换句话说，即便最坏情况下回退频繁发生，总回退量也在 O(n+m) 量级——因为 j 不可能无中生有地长高，每次回退的“高度”都来自之前匹配积攒的高度。加上构建 next 数组只需要扫描一遍模式串 O(m)，整个算法的复杂度便达到了优美的线性。

对比朴素算法 O(n×m) 的账本，KMP 等于把“反复上下山”变成“一次性爬完主线路”。对登山者而言，最坏情况下也不会因为某段岩壁设计得特别刁钻（全是重复字符）而体力崩盘——这就是线性保证的工程价值。

实战应用：三位登山者的工地

第一位登山者是文本编辑器的开发者。用户在几十万行代码的工程里按下 Ctrl+Shift+F 搜索某个函数名，编辑器底层需要快速定位所有出现位置。如果朴素匹配在最坏情况下卡顿，用户会觉得“这编辑器怎么这么慢”；KMP 的单遍扫描与线性保证让全局搜索即便面对恶意构造的重复文本也能稳定输出结果。

第二位登山者是生物信息工程师。高通量测序仪吐出海量的短序列片段（reads），每条只有几十到几百个碱基，却要定位到长达几十亿碱基的参考基因组上。这相当于在超长的“ACGT 岩壁”上寻找成千上万条短小路线。KMP 的线性特性让每条 reads 的定位既快又可预测，是序列比对工具中关键的精确匹配组件。

第三位登山者守护在网络安全一线。入侵检测系统（IDS）需要在每个网络包中快速扫描恶意特征串，攻击者经常故意构造大量重复字符来拖慢检测系统（正则拒绝服务攻击）。KMP 的最坏线性保证意味着：无论流量数据多么“滑腻”，特征匹配的时间都不会被恶意构造击穿，始终在可控范围内。此外，反垃圾邮件与敏感词过滤也依赖同样的精确匹配引擎。

代码实战：把岩钉表写进程序

最后，把登山者的整套策略翻译成 Python 代码。核心只有两个函数：build_next 负责边爬边钉岩钉，kmp_search 负责带着岩钉表完成一次扫描匹配。代码虽短，却完整复现了 next 构建、失配跳转、成功记录与继续搜索的全过程。

• nxt = [-1] — 初始化山脚哨兵，next[0] 固定为 -1。

• if j == -1 or pattern[i] == pattern[j]: — 无路可退或字符相等时，进入“延长公共前后缀”分支。

• nxt.append(j) — 记录下一位失配时的新跳转位置，相当于钉下一颗岩钉。

• j = nxt[j] — 字符不相等时沿 next 链回退，寻找更短的可复用前缀。

• while i < len(text): — 主串指针只前进不回退，体现“一次扫描”的核心。

• positions.append(i - j) — 当 j 走到模式串末尾时，计算并记录当前匹配起点。

• j = nxt[j] — 即使匹配成功，也要借助 next 继续寻找后续可能的匹配。

def build_next(pattern):    """构建 next 数组，next[j] 表示第 j 位失配时模式串应跳转的位置"""    nxt = [-1]    i, j = 0, -1    while i < len(pattern) - 1:        if j == -1 or pattern[i] == pattern[j]:            i += 1            j += 1            nxt.append(j)        else:            j = nxt[j]    return nxt  def kmp_search(text, pattern):    """在 text 中查找 pattern 的所有出现位置，返回起点下标列表"""    if not pattern:        return [0]    nxt = build_next(pattern)    i = j = 0    positions = []    while i < len(text):        if j == -1 or text[i] == pattern[j]:            i += 1            j += 1            if j == len(pattern):                positions.append(i - j)                j = nxt[j]        else:            j = nxt[j]    return positions  if __name__ == "__main__":    text = "ABABDABACDABABCABAB"    pattern = "ABABCABAB"    print("next:", build_next(pattern))    print("matches:", kmp_search(text, pattern))

AI 应用场景

Python 演示

def build_next(pattern):    """构建 next 数组，next[j] 表示第 j 位失配时模式串应跳转的位置"""    nxt = [-1]    i, j = 0, -1    while i < len(pattern) - 1:        if j == -1 or pattern[i] == pattern[j]:            i += 1            j += 1            nxt.append(j)        else:            j = nxt[j]    return nxt  def kmp_search(text, pattern):    """在 text 中查找 pattern 的所有出现位置，返回起点下标列表"""    if not pattern:        return [0]    nxt = build_next(pattern)    i = j = 0    positions = []    while i < len(text):        if j == -1 or text[i] == pattern[j]:            i += 1            j += 1            if j == len(pattern):                positions.append(i - j)                j = nxt[j]        else:            j = nxt[j]    return positions  if __name__ == "__main__":    text = "ABABDABACDABABCABAB"    pattern = "ABABCABAB"    print("next:", build_next(pattern))    print("matches:", kmp_search(text, pattern))

1. nxt = [-1]初始化山脚哨兵，next[0] 固定为 -1。
2. if j == -1 or pattern[i] == pattern[j]:无路可退或字符相等时，进入“延长公共前后缀”分支。
3. nxt.append(j)记录下一位失配时的新跳转位置，相当于钉下一颗岩钉。
4. j = nxt[j]字符不相等时沿 next 链回退，寻找更短的可复用前缀。
5. while i < len(text):主串指针只前进不回退，体现“一次扫描”的核心。
6. positions.append(i - j)当 j 走到模式串末尾时，计算并记录当前匹配起点。
7. j = nxt[j]即使匹配成功，也要借助 next 继续寻找后续可能的匹配。

常见误区

面试题