KMP string match algorithm in Python
You can see your implementation is wrong by examining the simplest case, a pattern P consisted of a repeated single character: "AAAAA". At every point of the failure function, the length of the largest proper prefix of P which is also a proper suffix of P is ever-increasing: [-1, 0, 1, 2, 3] - however your implementation computes [-1, -1, -1, -1, -1].

Translating the pseudocode in the Wikipedia entry into Python gives us:

def kmp_table(pattern):
    if len(pattern) == 0:
        return None

    ff = [0] * len(pattern) # FF for failure function
    ff[0] = -1
    pos = 2
    cnd = 0

    while pos &lt; len(pattern):
        if pattern[pos - 1] == pattern[cnd]:
            cnd += 1
            ff[pos] = cnd
            pos += 1
        elif cnd &gt; 0:
            cnd = ff[cnd]
        else:
            ff[pos] = 0
            pos += 1

    return ff