KMP算法是字符串匹配的一种改进算法，在1977年由D. E. Knuth，J. H. Morris和V. R. Pratt一起提出，并以他们名字的首字母命名。和朴素的模式匹配算法相比，KMP算法最大的特点就是主串指针不回溯。它利用已经得到的“部分匹配”信息来减少不必要的比较而加快字符串的匹配速度。 KMP算法的本质 KMP算法本质上是实现了对自动机的模拟。它通过构造一个有限自动机来搜寻某给定的模式在正文中出现的位置。整个算法的核心就是对自动机的构建（或前缀函数的构建，KMP算法不用计算变迁函数，而是根据模式预先计算出一个辅助函数next来实现更快速的状态切换），当完成有限自动机的构建之后对主串的搜寻就显得很简单了。 前缀函数next的构建 模式的前缀函数包含有模式与其自身的位移进行匹配的信息。这些信息可用于避免在朴素的模式匹配算法中对无用位移的测试。比如主串和模式串在主串指针为Ti、模式串指针为Pj处匹配失败时，可以主串指针不回溯并直接取next函数的值next[j] = k将模式串向右滑动到第k个字符处重新开始比较，而不用去做无用位移的测试。只是这样的操作能成立k必须要满足一定的条件，如下所示： 首先，如果模式串能直接向右滑动到第k个字符处重新开始比较则说明模式串中的前k-1个字符必然已经和主串匹配了，也即必然已经有下面式子，且为了能最大化的向右移动则不能存在更大的k’满足下面式子：