KMP算法的next求不对
KMP算法的next得出的答案不对，能帮忙看下哪里不对吗def getnext(t):
n = len(t)
next =
j = 0# i：前缀尾，j：后缀尾
for i in range(1,n):
while (t != t) and (j > 0):
j = next
if t == t:
j += 1
next = j
return next
t = input("输入子串：")
res = getnext(t)
print(res) 在你提供的代码中，有一个问题导致了next数组求解不正确。问题出现在while循环内部的判断条件上。
请将以下代码段：
while (t[ i] != t) and (j > 0):
j = next
修改为：
while (j > 0) and (t[ i] != t):
j = next
这样修改后，再运行代码求解KMP算法的next数组应该能够得到正确的结果。
修改后的完整代码如下所示：
def getnext(t):
n = len(t)
next =
j = 0# i：前缀尾，j：后缀尾
for i in range(1, n):
while (j > 0) and (t[ i] != t):
j = next
if t[ i] == t:
j += 1
next[ i] = j
return next
t = input("输入子串：")
res = getnext(t)
print(res)
希望这次修改能够解决你的问题。如果还有其他疑问，请随时提问。
如果问题已经解决，请设置最佳答案 问题出在while循环的条件判断上。在KMP算法中，当t[ i] != t时，需要将j回溯到next的位置，而不是直接回溯到j-1的位置。所以需要将while循环的条件改为t[ i] != t and j > 0，并将j回溯到next的位置。
以下是修改后的代码：
def getnext(t):
n = len(t)
next =
j = 0# i：前缀尾，j：后缀尾
for i in range(1, n):
while (t[ i] != t) and (j > 0):
j = next
if t[ i] == t:
j += 1
next[ i] = j
return next
t = input("输入子串：")
res = getnext(t)
print(res)
希望能帮到你！ isdkz 发表于 2023-9-2 15:48
问题出在while循环的条件判断上。在KMP算法中，当t[ i] != t时，需要将j回溯到next的位置，而不是 ...
也不对啊，修改后的代码和我发的一模一样啊 isdkz 发表于 2023-9-2 15:48
问题出在while循环的条件判断上。在KMP算法中，当t[ i] != t时，需要将j回溯到next的位置，而不是 ...
okok,没问题了 当您使用KMP算法时，如果next数组得出的答案不正确，可能是在计算next数组时出现了错误。下面是一种常见的计算next数组的方法，您可以检查是否有误：
假设待匹配的字符串为pattern，长度为m。
1. 初始化一个长度为m的next数组，将第一个元素next设置为-1。
2. 设置两个指针i和j，分别指向pattern的第一个字符和第二个字符。
3. 进入循环，判断j是否等于m-1，如果是，则退出循环。
4. 在循环中，判断pattern和pattern是否相等：
- 如果相等，则将next设置为i，并将i和j分别增加1。
- 如果不相等，则将i更新为next（即回溯到前一个匹配位置），直到i=-1或者pattern==pattern为止。
5. 继续循环，重复步骤4。
6. 循环结束后，返回得到的next数组。
您可以按照上述步骤检查代码中计算next数组的部分，确保每一步都正确执行。如果仍然无法找到错误，请提供您的代码片段，我将尽力帮助您找出问题所在。
此内容为ChatGPT回答，如果胡说八道，请不要理会
如果对你有帮助，请设置一个最佳答案！
页:
[1]