面试里背得最顺的一句话是："朴素搜索是 O(n·m)，KMP 是 O(n+m)，所以 KMP 一定更快。"我一度也这么信。直到上周把一个 640KB 的日志做关键字提取，手写的 KMP 比同事三行 indexOf 慢了整整一个数量级——这不对劲。于是我把朴素、KMP、Boyer-Moore-Horspool（BMH）和 V8 内置 String.indexOf 拉到同一张基准上，用可控文本跑了中位数，结论和教科书不太一样。

背景：为什么字符串搜索值得较真

字符串搜索是工程里出现频率最高的"小操作"：日志关键字提取、模板引擎匹配、协议解析、浏览器地址栏高亮、IDE 符号查找……单次看着便宜，可一旦放进热路径（每行日志、每个请求、每个 token），复杂度的常数因子会被放大成实打实的延迟。

问题就出在"共识"两个字。教科书把朴素算法钉在 O(n·m) 的耻辱柱上，把 KMP 捧成 O(n+m) 的优等生，却很少讲清楚：O(n+m) 的"保证"到底在什么输入下才兑现，又是什么让 KMP 在另一些输入下反而更慢。本次实测想回答的就是这件事。

解剖：朴素、KMP、BMH 到底差在哪

三种手写的算法，差异全在"失配后怎么移动指针"：

• 朴素（Brute Force）：文本每个位置 i 都从头比对 pattern，失配就 i+1 重来。最坏情况每移一位都要比 m 个字符，于是 O(n·m)。但它的隐藏优势是：在"几乎不匹配"的真实文本里，第一次比对就失败，实际只做约 2n 次比较——常数极小。
• KMP：预处理 pattern 出一张 lps（最长公共前后缀）表，失配时利用已匹配前缀跳过不必比的位置，搜索阶段严格 O(n)。代价是每次失配都要查 lps 表、维护两个指针，常数比朴素大。
• BMH（Boyer-Moore-Horspool）：只看 pattern 最后一个字符做"坏字符"跳转，平均能一次跳过接近 m 个字符，实际表现常常优于 KMP，且代码更短。
• 内置 indexOf：V8 并不是教科书实现，而是 SIMD + Two-Way 风格的工业级搜索，单条指令比对多个字节，是这次的"天花板"基线。

图1：四种字符串搜索算法的机制差异。KMP 的"快"来自失配时的前缀复用，但每次复用都要付出查表与双指针的常数成本。

实证一：随机文本里，KMP 并没有更快

先用"最像生产"的输入：10 万字符的随机英文文本、pattern 搜不到（典型"找关键字但不存在"的场景）。Node v22、固定种子、每配置取中位数。结果（单次搜索耗时，毫秒）：

文本规模	pattern 长	朴素	KMP	BMH	indexOf
10K	5	0.0098	0.0224	0.0075	0.0013
100K	100	0.3637	0.2817	0.0132	0.0092
1M	100	6.5701	3.9802	0.1862	0.1065

关键发现：在"搜不到"的随机文本里，KMP 并不稳赢朴素。pattern 只有 5 个字符时，KMP 反而比朴素慢 2.3 倍（0.0224 vs 0.0098 ms）——因为朴素几乎第一步就失配，而 KMP 的查表与双指针纯属 overhead。即便在 1M 规模，朴素与 KMP 的差距也只在 1.6 倍以内来回拉锯。换句话说，O(n+m) 的"保证"在随机文本里几乎兑现不出收益。

图2：随机文本、短 pattern 的场景下，KMP 的常数开销让它跑不过朴素；BMH 与 indexOf 则早已把两者甩开。

实证二：对抗文本里，朴素搜索当场爆炸

那 KMP 的保证什么时候才兑现？答案是：当文本逼出朴素的最坏情况——大量"部分匹配"。构造文本全是 'a'，pattern 是 'a'×(m-1)+'b'（永不整段命中，但每个对齐都要比 m−1 个 'a' 才失败），朴素立刻退化成 O(n·m)：

文本规模	pattern 长	朴素	KMP	BMH	indexOf
10K	100	4.5115	0.0756	0.0542	0.0255
100K	100	50.6157	0.7289	0.7110	0.2606
200K	100	74.7953	2.2145	0.8962	0.5161

100KB 的 'a' 文本、pattern 长 100 时，朴素 50.6ms，KMP 0.73ms——朴素慢了 69 倍。这就是 O(n+m) 保证的意义：它把"对手能构造的最坏输入"从指数级拉回线性。但注意，BMH 和 indexOf 同样扛住了这场爆炸，KMP 并非唯一的解药。

图3：当文本制造大量部分匹配，朴素的 O(n·m) 最坏情况被彻底激活；KMP/BMH/indexOf 都保持线性，但朴素一支独大。

实证三：真正赢麻的是 BMH 和内置 indexOf

把三张表合起来看，真正的赢家从来不是 KMP。在 1M 随机文本、pattern 长 100 的场景里：IndexOf 0.107ms，BMH 0.186ms，KMP 3.98ms，朴素 6.57ms。内置 indexOf 比手写的 KMP 快 37 倍、比朴素快 62 倍；BMH 也比 KMP 快 21 倍。哪怕是 KMP 的"主场"对抗文本，IndexOf 仍是最快的那个（0.26ms vs KMP 0.73ms）。

原因不难想：V8 的 indexOf 用 SIMD 一次比对十几个字节，BMH 靠坏字符跳转几乎跳着走，而 KMP 再怎么优化也是"逐字符 + 查表"。手写 KMP 的价值，只存在于"你不能调内置、又没法引入 BMH"的极少数受限环境。

图4：综合来看，内置 indexOf 与 BMH 把 KMP 和朴素同时甩开；手写 KMP 在性能上并不占优。

局限：这次没测什么

诚实边界，避免被当成"银弹"：

• 只测了"单 pattern、单次搜索"。多关键字（如一次性匹配上千条攻击特征）该上 Aho-Corasick，那是另一篇文章。
• 文本是内存字符串；超大规模外存搜索要考虑 IO 而非算法常数。
• BMH 在极小字母表（如 DNA 的 A/C/G/T）上坏字符跳转收益下降，KMP/Z 算法在小字母表更稳——本次没覆盖。
• 数字来自单台机器（Windows / AMD64 / Node v22）的中位数，不同 V8 版本、不同 CPU 会有浮动，但相对排序稳定。

结论与下一步

一句话方法论：别再为了"O(n+m)"手写 KMP。普通搜索直接用内置 indexOf；要手写就选 BMH；只有多 pattern 才考虑 Aho-Corasick。KMP 的复杂度保证只在"对手能构造最坏输入"的对抗场景下才值钱，而那种场景下 BMH 和内置实现同样线性，KMP 并不特殊。

开源地址：

• 矩阵门户：https://github.com/wangzifan396-wzf/WB
• 单文件工具聚合器：https://github.com/wangzifan396-wzf/nano-workbench
• GitHub 组织主页：https://github.com/wangzifan396-wzf