KMP 算法（全称 Knuth-Morris-Pratt 字符串查找算法，由三位发明者的姓氏命名），是一种可以在线性时间内从文本串 $s$ 中查找模式串 $p$ 的算法。

**推荐视频教程：**https://b23.tv/vrE7iMZ

很容易想到一种暴力做法，一步一步的和模式串比对，如果不匹配从跳回开始跳的位置的下一个字符，重新开始比对，这样做的时间复杂度为 $O(nm)$，是非常慢的算法。

我们想，既然在字符串在比对失败的时候已经知道读过哪些字符了，能不能避免跳回去再重新匹配的步骤呢，于是就有了线性时间复杂度的 KMP 算法。

KMP 算法与暴力做法的不同之处在于，他会花费一些空间来记录一些信息（即 $next$ 数组），这同样是 KMP 算法的精髓所在。