KMP算法的next求不对

15588686105

KMP算法的next得出的答案不对，能帮忙看下哪里不对吗

def getnext(t):
    n = len(t)
    next = [0 for i in range(n)]
    j = 0  # i：前缀尾，j：后缀尾
    for i in range(1,n):
        while (t[i] != t[j]) and (j > 0):
            j = next[j - 1]
        if t[i] == t[j]:
            j += 1
        next[i] = j

    return next

t = input("输入子串：")

res = getnext(t)
print(res)

陶远航

在你提供的代码中，有一个问题导致了next数组求解不正确。问题出现在while循环内部的判断条件上。

请将以下代码段：

while (t[ i] != t[j]) and (j > 0):
    j = next[j - 1]

修改为：

while (j > 0) and (t[ i] != t[j]):
    j = next[j - 1]

这样修改后，再运行代码求解KMP算法的next数组应该能够得到正确的结果。

修改后的完整代码如下所示：

def getnext(t):
    n = len(t)
    next = [0 for i in range(n)]
    j = 0  # i：前缀尾，j：后缀尾
    for i in range(1, n):
        while (j > 0) and (t[ i] != t[j]):
            j = next[j - 1]
        if t[ i] == t[j]:
            j += 1
        next[ i] = j
    return next

t = input("输入子串：")
res = getnext(t)
print(res)

希望这次修改能够解决你的问题。如果还有其他疑问，请随时提问。
如果问题已经解决，请设置最佳答案

isdkz

问题出在while循环的条件判断上。在KMP算法中，当t[ i] != t[j]时，需要将j回溯到next[j-1]的位置，而不是直接回溯到j-1的位置。所以需要将while循环的条件改为t[ i] != t[j] and j > 0，并将j回溯到next[j-1]的位置。

以下是修改后的代码：

def getnext(t):
    n = len(t)
    next = [0 for i in range(n)]
    j = 0  # i：前缀尾，j：后缀尾
    for i in range(1, n):
        while (t[ i] != t[j]) and (j > 0):
            j = next[j - 1]
        if t[ i] == t[j]:
            j += 1
        next[ i] = j

    return next

t = input("输入子串：")
res = getnext(t)
print(res)

希望能帮到你！

15588686105

isdkz 发表于 2023-9-2 15:48
问题出在while循环的条件判断上。在KMP算法中，当t[ i] != t[j]时，需要将j回溯到next[j-1]的位置，而不是 ...

也不对啊，修改后的代码和我发的一模一样啊

15588686105

isdkz 发表于 2023-9-2 15:48
问题出在while循环的条件判断上。在KMP算法中，当t[ i] != t[j]时，需要将j回溯到next[j-1]的位置，而不是 ...

okok,没问题了

琅琊王朝

当您使用KMP算法时，如果next数组得出的答案不正确，可能是在计算next数组时出现了错误。下面是一种常见的计算next数组的方法，您可以检查是否有误：

假设待匹配的字符串为pattern，长度为m。

1. 初始化一个长度为m的next数组，将第一个元素next[0]设置为-1。

2. 设置两个指针i和j，分别指向pattern的第一个字符和第二个字符。

3. 进入循环，判断j是否等于m-1，如果是，则退出循环。

4. 在循环中，判断pattern[i]和pattern[j]是否相等：
   - 如果相等，则将next[j+1]设置为i，并将i和j分别增加1。
   - 如果不相等，则将i更新为next[i]（即回溯到前一个匹配位置），直到i=-1或者pattern[i]==pattern[j]为止。

5. 继续循环，重复步骤4。

6. 循环结束后，返回得到的next数组。

您可以按照上述步骤检查代码中计算next数组的部分，确保每一步都正确执行。如果仍然无法找到错误，请提供您的代码片段，我将尽力帮助您找出问题所在。
此内容为ChatGPT回答，如果胡说八道，请不要理会
如果对你有帮助，请设置一个最佳答案！