克努斯-莫里斯-普拉特算法

计算机科学中,Knuth-Morris-Pratt字符串查找算法(简称为KMP算法)可在一个主文本字符串S内查找一个W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现,从而避免重新检查先前匹配的字符

这个算法是由高德纳沃恩·普拉特英语Vaughan Pratt在1974年构思,同年詹姆斯·H·莫里斯英语James H. Morris也独立地设计出该算法,最终由三人于1977年联合发表。

注意:在本文中,我们将使用始于零的数组来表示我们的字符串。所以在下面例子中,我们用W[2]来表示字符串W中的字符'C'。这种表示遵从C语言的语法。