KMP Border Chain Lengths

Problem

For every prefix pattern[:i] with i from 1 to n, count its proper borders by following the KMP failure function: start at j = pi[i - 1] and count each positive j reached through j = pi[j - 1]. Return the list of chain lengths for i = 1..n, and [] for an empty pattern. Build pi with the standard prefix-function loop.

Hint

Every proper border of a prefix is found by repeatedly following the failure link of the previous border.

Test cases

case 1

in: ["aabaa"]

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

case 2

in: ["ababab"]

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

case 3

in: ["aaaa"]

expected: [0,1,2,3]

case 4

in: ["abc"]

expected: [0,0,0]

case 5

in: [""]

expected: []

Starter codePython

def kmp_border_chain_lengths(pattern):
    # Your code here
    pass

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