KMP string match algorithm in Python

Question

Write the implementation for generating pattern part, and did some testing, seems good to me. But not sure if any functional bugs? If anyone find a functional bug, appreciate for the insights.

def findPattern(pattern):

    j = -1
    next = [-1] * len(pattern)
    i = 0 # next[0] is always -1, by KMP definition

    while (i+1 < len(pattern)):
        if (j == -1) or (pattern[j] == pattern[i]):
            i += 1
            j += 1
            if pattern[i] != pattern[j]:
                next[i] = j
            else:
                next[i] = next[j]
        else:
            j = next[j]

    return next

if __name__ == "__main__":

    print findPattern("aaaab")
    print findPattern("abaabc")

Answer 1

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 < len(pattern):
        if pattern[pos - 1] == pattern[cnd]:
            cnd += 1
            ff[pos] = cnd
            pos += 1
        elif cnd > 0:
            cnd = ff[cnd]
        else:
            ff[pos] = 0
            pos += 1

    return ff