KMP实现的效果就是，当匹配失败时，不是简单地从下一个字符起重新匹配，而是以O(1)的复杂度定位到下一个起始点，而且保证主串不折回，从而最多2k次即能完成匹配。

while m + i is less than the length of S, do:
    if W[i] = S[m + i],
        let i ← i + 1
        if i equals the length of W,
            return m
    otherwise,
        let m ← m + i - T[i],
        if T[i] is greater than -1,
            let i ← T[i]

其中m为主串当前位置，i为模式串当前位置，S为主串，W为模式串。

这里面关键就在于如何O(1)的复杂度定位到下一个起始点，而这个问题其实与主串无关，而只取决于模式串，可以发现其中的递归关系：

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

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

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