我在python中的计算前缀函数实现给出了错误的结果

发布时间：2020-12-20 11:57:30 所属栏目：Python 来源：网络整理

导读：我在 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): w

我在 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,1,2,0].
但正确的结果必须是：[0,3,1]

pseudoc code is available here.它在第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]

(正如这个程序产生的那样),而不是

[0,1,1]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!