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

在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。
这个算法是由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终由三人于1977年联合发表。
注意：在本文中，我们将使用始于零的数组来表示我们的字符串。所以在下面例子中，我们用W[2]来表示字符串W中的字符'C'。这种表示遵从C语言的语法。

部分匹配表

部分匹配表，又称为失配函数，作用是让算法无需多次匹配S中的任何字符。能够实现线性时间搜索的关键是在主串的一些字段中检查模式串的初始字段，我们可以确切地知道在当前位置之前的一个潜在匹配的位置。换句话说，在不错过任何潜在匹配的情况下，我们"预搜索"这个模式串本身并将其译成一个包含所有可能失配的位置对应可以绕过最多无效字符的列表。
对于W中的任何位置，我们都希望能够查询那个位置前（不包括那个位置）有可能的W的最长初始字段的长度，而不是从W[0]开始失配的整个字段，这长度就是我们查找下一个匹配时回退的距离。因此T[i]是W的可能的适当初始字段同时也是结束于W[i - 1]的子串的最大长度。我们使空串长度是0。当一个失配出现在模式串的最开始，这是特殊情况（无法回退），我们设置T[0] = -1，在下面讨论。

创建表算法的伪代码的解释

上面的例子以最少的复杂步骤展示了组织这个表格的一般性方法。这么做的原理是对整体的搜索：大多数工作已经在检测到当前位置的时候做完了，剩下需要做的很少。略微复杂的一点是找到一个共同前后缀。这就需要有一些初始化的代码。
algorithm kmp_table:
    input:
        an array of characters, W (the word to be analyzed)
        an array of integers, T (the table to be filled)
    output:
        nothing (but during operation, it populates the table)

    define variables:
        an integer, pos ← 2 (the current position we are computing in T)
        an integer, cnd ← 0 (the zero-based index in W of the next 
character of the current candidate substring)

    (the first few values are fixed but different from what the algorithm 
might suggest)
    let T[0] ← -1, T[1] ← 0

    while pos < length(W) do
        (first case: the substring continues)
        if W[pos - 1] = W[cnd] then
            let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

        (second case: it doesn't, but we can fall back)
        else if cnd > 0 then
            let cnd ← T[cnd]

        (third case: we have run out of candidates.  Note cnd = 0)
        else
            let T[pos] ← 0, pos ← pos + 1

创建表的算法的效率

创建表的算法的复杂度是O(n)，其中n是W的长度。除去一些初始化的工作，所有工作都是在while循环中完成的，足够说明这个循环执行用了O(n)的时间，同时还会检查pos和pos - cnd的大小。在第一个分支里，pos - cnd被保留，而pos与cnd同时递增，自然，pos增加了。在第二个分支里，cnd被T[cnd]所替代，即以上总是严格低于cnd，从而增加了pos - cnd。在第三个分支里，pos增加了，而cnd没有，所以pos和pos - cnd都增加了。因为pos ≥ pos - cnd，即在每一个阶段要么pos增加，要么pos的一个下界增加；所以既然此算法只要有pos = n就终止了，这个循环必然最多在2n次迭代后终止，因为pos - cnd从1开始。因此创建表的算法的复杂度是O(n)。