Knuth–Morris–Pratt 算法

克努特–莫里斯–普拉特算法
术语名称	克努特–莫里斯–普拉特算法
英语名称	Knuth–Morris–Pratt algorithm
别名	KMP算法, KMP algorithm

'‌KMP 算法'(Knuth–Morris–Pratt algorithm, KMP algorithm)是一种高效的字符串匹配算法，名称来自发明人。

与暴力搜索，即每个位置尝试匹配相对，其核心思想是在进行匹配时记录同一段字符串的公共前后缀信息，从而在判断匹配失败时，直接按照当前位置已经匹配到了的前缀长度进行回溯，不需要匹配中间的部分，以减少匹配过程中的回溯次数，显著提升匹配效率。