kmp算法的有关问题

Question

请问一下关于以下题我写的代码哪里出错了？？请指正，非常感谢！

Answer 1

【以下回答由 GPT 生成】

你的代码逻辑上没有问题，但是在computeLps函数中，你没有处理正确的边界情况。在该函数中，i从1开始，但你没有处理lps[0]的情况。另外，在kmp函数的最后，你没有返回任何值。我为你修改了代码并提供了改正建议，如下所示：

def kmp(pattern, text):
    n = len(pattern)
    m = len(text)
    lps = [0] * n
    i, j = 0, 0

    computeLps(pattern, n, lps)

    while i < m:
        if pattern[j] == text[i]:
            i += 1
            j += 1
            if j == n:
                print("Pattern found at index", i - j)
                j = lps[j - 1]
        elif i < m and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

def computeLps(pattern, n, lps):
    length = 0
    i = 1

    while i < n:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
                length = 0

pattern = "ABABDABACDABABCABAB"
text = "ABCABCDABABCDABCDABDE"
kmp(pattern, text)

修改建议： - 在computeLps函数的最后，增加length = 0的语句，以处理lps[0]的情况。 - 在kmp函数中，当找到完整的匹配时，将判断j == n的语句放在i和j的自增语句之后。

这样就可以保证代码逻辑的正确性。现在你可以尝试运行代码并检查是否可以正确地输出结果。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7525206
• 这篇博客你也可以参考下：kmp算法原理及代码解释，通俗易懂
• 您还可以看一下 孙玖祥老师的图解数据结构与算法课程中的 KMP算法思想-动画演示小节, 巩固相关知识点
  
• 除此之外, 这篇博客: KMP算法真的有这么难吗？（清晰详细版）中的 部分匹配值的作用 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^