KMP Failure Function

Problem

Compute the KMP prefix function of pattern: table[i] is the length of the longest proper prefix of pattern[:i+1] that is also a suffix.

Use the standard linear scan that falls back through earlier table values on a mismatch. Return an empty list for an empty pattern.

Hint

On a mismatch, fall back to the longest border of the prefix already matched.

case 1

in: ["ababaca"]

expected: [0,0,1,2,3,0,1]

case 2

in: ["aabaaab"]

expected: [0,1,0,1,2,2,3]

case 3

in: [""]

expected: []

case 4

in: ["a"]

expected: [0]

case 5

in: ["aaaa"]

expected: [0,1,2,3]

Starter codePython

def kmp_failure_function(pattern):
    # Your code here
    pass

5 test cases · run your code against them in the editor