My Compute Prefix Function implementation in python gives false result

Question

I implemented the Compute-Prefix-Function in Python, but it gives me false result (I am beginner in python) Can somebody help me what is wrong in my implementation compare with the pseudo code?

def pi_prefix_fuggveny(pattern):
    P = list(pattern)
    m = len(P)
    a = [0] * m
    k = 0

    for q in range(2, m):
        while k > 0 and P[k+1] != P[q]:
            k = a[k]
        if P[k+1] == P[q]:
            k = k + 1
        a[q] = k

    return a

print pi_prefix_fuggveny("ababaca")

The result is: [0, 0, 0, 1, 2, 0, 0]. But the correct result must be: [0, 0, 1, 2, 3, 1, 1]

The pseudoc code is available here. It is on the 7th page

Answer 1

The issue is that the paper you linked is using 1-indexed arrays, whereas we typically use 0-indexed arrays in the coding world. I adjusted the indexes accordingly:

def pi_prefix_fuggveny(pattern):
    P = list(pattern)
    m = len(pattern)
    a = [0] * m
    k = 0

    for q in range(2, m + 1):
        while k > 0 and P[k] != P[q - 1]:
            k = a[k - 1]
        if P[k] == P[q - 1]:
            k += 1
        a[q - 1] = k

    return a


print(pi_prefix_fuggveny("ababaca"))

I also think that the paper makes a mistake and the output should be:

[0, 0, 1, 2, 3, 0, 1]

(as this program produces), not

[0, 0, 1, 2, 3, 1, 1]