Knuth–Morris–Pratt 字符串查找算法在一个主"文本字符串" S 内查找一个"词"的出现，通过采用一种简单的观察，在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始，以此越过对以前匹配的字符的重新检查。
算法是由 高德纳 和 Pratt 以及独立地由 J. H. Morris 在1977年发明的，但是三人联合发表了它。
在本文中，我们将使用基于零的数组来表示我们的字符串；所以下面例子中 W 中的 'C' 将被表示为 W[2]。一般来说，表示法服从 C 语法，在它不是太不合情理的时候。
