在电脑科学中,克努斯-莫里斯-普拉特字符串查找算法(英语:Knuth–Morris–Pratt algorithm,简称为KMP算法)可在一个字符串S
内查找一个词W
的出现位置。一个词在不匹配时本身就包含足够的资讯来确定下一个匹配可能的开始位置,此算法利用这一特性以避免重新检查先前配对的字符。
- 在本文中,将使用始于零的数组来表示字符串。比如,若字符串
S = "ABC"
,则S[2]
表示字符'C'
。这种表示方法与C语言一致。
这个算法由高德纳和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。