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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了我在python中的计算前缀函数实现给出了错误的结果，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含886字，纯文字阅读大概需要2分钟。

内容图文

我在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 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, 2, 3, 0, 1]

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

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

内容总结

以上是互联网集市为您收集整理的我在python中的计算前缀函数实现给出了错误的结果全部内容，希望文章能够帮你解决我在python中的计算前缀函数实现给出了错误的结果所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端