KMP 算法

定义

KMP 算法是一种线性时间的字符串匹配算法,由 Donald Knuth、James Morris 和 Vaughan Pratt 于 1977 年发表,用于在文本串中查找模式串的出现位置。

原理

核心是预处理模式串,构造前缀函数(失配数组,常称 next 数组),记录每个前缀的最长相等真前后缀长度。匹配失败时,文本指针不回退,模式指针依据 next 数组跳转到合适位置继续比较,从而将整体复杂度降为 O(n+m),n、m 分别为文本与模式长度。

应用

用于文本编辑器查找、DNA 序列匹配等场景;其前缀函数本身也是解决字符串周期、循环节等问题的重要工具。

优缺点

优点是最坏情况下仍保持线性、无需回退输入(适合流式处理);缺点是实际平均性能常不如 Boyer-Moore 类算法,且 next 数组的构造与理解相对抽象。