3

我在 Python 中实现了 Compute-Prefix-Function，但它给了我错误的结果（我是 python 的初学者） 有人可以帮我与伪代码相比，我的实现有什么问题吗？

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")

结果是：[0, 0, 0, 1, 2, 0, 0]。但正确的结果必须是：[0, 0, 1, 2, 3, 1, 1]

此处提供了pseudoc 代码。它在第 7 页

4

1 回答 1

7

问题是您链接的论文使用的是 1 索引数组，而我们通常在编码世界中使用 0 索引数组。我相应地调整了索引：

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"))

我也认为论文犯了一个错误，输出应该是：

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

（正如这个程序产生的那样），而不是

[0, 0, 1, 2, 3, 1 , 1]
于 2017-01-26T20:45:53.137 回答