字符串匹配基础：朴素匹配与 KMP

学字符串时，我们已经提到过一个非常核心的问题：

在一个主串中，如何高效找到某个模式串出现的位置？

这个问题看起来简单，但实际上几乎贯穿了所有文本处理系统：

  • 编辑器搜索；
  • 日志关键字定位；
  • 编译器词法处理；
  • 协议文本分析；
  • 搜索系统中的基础匹配。

最直观的做法当然是：主串从左到右逐位尝试，模式串一个个比对。这个方法叫朴素匹配。它简单直接，但效率并不总理想。KMP 则是在此基础上做的一个非常经典的优化：

  • 不再让模式串一失配就完全从头开始；
  • 而是利用模式串本身的重复结构，跳过一些明显不必重比的部分。

所以理解 KMP 的关键，不是死记 next 数组，而是看懂：为什么失配后还能“不回退主串”，以及这种跳跃到底利用了什么信息。

一、什么是字符串匹配问题

字符串匹配通常指的是：

  • 给定主串 S；
  • 给定模式串 P；
  • 找到 P 在 S 中第一次或所有出现的位置。

最朴素的问题表述看似简单，但一旦字符串很长、查询很频繁，匹配效率就会非常重要。

二、什么是朴素匹配算法

朴素匹配，也常叫暴力匹配，思路很直接：

  1. 让模式串从主串的某个起始位置对齐；
  2. 从前往后逐字符比较；
  3. 如果全部匹配成功，就得到答案；
  4. 一旦失配，就让模式串整体右移一位，重新开始比较。

它最大的优点是：

  • 简单；
  • 容易实现；
  • 不需要额外预处理。

但缺点也很明显：

  • 可能会发生大量重复比较；
  • 某些情况下效率很差。

三、朴素匹配为什么会有重复比较

例如主串和模式串前面有一大段已经匹配成功，但在后面某一位失配时，朴素算法会：

  • 让模式串整体右移一位；
  • 然后从头重新比较。

这会导致刚刚已经知道的信息被白白浪费。

也就是说，朴素匹配的问题不在于“能不能找到”，而在于：

它没有利用已经比较过的结果。

四、KMP 想解决什么问题

KMP 的核心目标非常明确：

当失配发生时，不让模式串盲目只右移一位，而是根据模式串自身结构，直接移动到一个“仍然可能匹配”的位置。

更关键的是，它希望做到：

  • 主串指针不回退；
  • 已经比较过的主串字符尽量不再重复比较。

这就是 KMP 最经典、最有力量的地方。

五、KMP 为什么能不回退主串

因为它在匹配之前，先对模式串本身做了一次预处理，找出了：

  • 某个位置失配时；
  • 模式串前面那一段中；
  • 哪个前缀和后缀是相同的；
  • 从而知道模式串可以直接跳到哪里继续尝试。

换句话说，KMP 并不是“更聪明地看主串”，而是：

  • 先把模式串研究透；
  • 然后在匹配过程中利用这些结构信息省掉重复比较。

六、什么是前缀、后缀和部分匹配信息

理解 KMP，必须先理解这几个词。

1. 前缀

一个字符串从开头开始取的连续子串，但通常不包括整个串本身。

2. 后缀

一个字符串从结尾开始取的连续子串，但通常不包括整个串本身。

3. 最长相等前后缀

在某个前缀子串中，同时是前缀又是后缀的最长公共部分。

例如对于某些模式串前缀，可能存在：

  • 前面一段和结尾一段一样；
  • 这就说明失配后，模式串不必完全从头再来。

这正是 next 数组或前缀函数背后的核心信息。

七、KMP 中的 next 数组到底记录了什么

可以把 next 数组理解成：

当模式串在某个位置失配时，下一步模式串指针应该回到哪里，才能继续保持已经确认过的匹配信息不浪费。

从更本质的角度讲，它记录的就是：

  • 当前前缀中最长相等前后缀长度；
  • 或对应可回退到的位置。

所以 next 不是一个凭空出现的技巧数组，而是模式串自身重复结构的摘要。

八、KMP 的匹配过程怎么理解

匹配时通常有两个指针：

  • i 指向主串；
  • j 指向模式串。

过程通常是：

  • 如果字符相同，就一起向后；
  • 如果失配且 j > 0，就根据 next[j] 调整 j；
  • 如果 j == 0 还失配，就只移动主串指针；
  • 直到模式串全部匹配完成。

关键就在于：

  • 主串 i 不往回退；
  • 模式串 j 根据结构信息跳转。

这让整体匹配效率大幅提升。

九、KMP 的时间复杂度为什么是 O(n + m)

设主串长度为 n，模式串长度为 m。

  • 构造 next 数组通常是 O(m)；
  • 正式匹配通常是 O(n) 级别；
  • 因为主串指针整体只前进不回退。

于是总复杂度通常写成：

1
O(n + m)

这比某些情况下可能达到 O(nm) 的朴素匹配要稳定得多。

十、KMP 最值得学到的不是模板，而是什么

其实是一个非常重要的思想：

当问题中存在重复结构时，应该尽量把已经获得的信息保留下来，避免重复计算。

KMP 表面上是字符串算法，背后体现的其实是非常普遍的算法思维：

  • 预处理；
  • 利用部分结果；
  • 在失配或回退时尽量不要完全重来。

这类思想在后面的动态规划、自动机、多模式匹配里都会反复出现。

十一、KMP 在真实场景里常见吗

如果只是日常业务开发，很多时候你会直接调用标准库的字符串查找函数，不一定自己手写 KMP。但从理解层面，它依然很重要，因为：

  • 它是最经典的单模式匹配算法之一；
  • 它训练你真正理解字符串重复结构；
  • 它是很多后续字符串算法和自动机构造的基础认知。

所以就算以后不常手写，也很值得吃透它的原理。

十二、学习 KMP 时最容易踩的坑

1. 死背 next 数组模板

这是最常见的问题。模板能背下来，但一问为什么就说不清。

2. 分不清 next 数组不同定义版本

不同教材对 next、前缀函数、失配函数的下标定义可能不同，关键是理解本质，不要被形式绕晕。

3. 只会写匹配，不理解为什么主串可以不回退

这一点才是 KMP 的灵魂。

4. 误以为 KMP 永远是所有场景最佳选择

后面还有 BM、Sunday、Rabin-Karp 等，它们在不同场景下也有优势。

总结

朴素匹配与 KMP 的意义，不只是因为它们是字符串算法入门，而是因为它们非常清楚地展示了“从暴力到结构利用”的优化路径。真正值得先建立起来的，是这些核心认识：

  • 字符串匹配问题的核心是在主串中定位模式串；
  • 朴素匹配简单直接，但会产生大量重复比较；
  • KMP 通过预处理模式串的前后缀结构，避免失配后完全重来；
  • next 数组本质上记录的是模式串自身的重复信息；
  • KMP 的高效，来自“主串不回退、模式串智能跳转”；
  • 真正学会 KMP，不是记住代码模板，而是理解“为什么失配后还能继续利用已经匹配过的信息”。

把这一篇理解透之后，后面再去学 BM、Sunday、Rabin-Karp 或 Aho-Corasick 时，你会更容易看到：各种匹配算法虽然技巧不同，但都在围绕一个核心目标努力，那就是尽量少做无意义的字符比较。

参考资源：