鱼C论坛

 找回密码
 立即注册
查看: 1872|回复: 5

KMP算法的next求不对

[复制链接]
发表于 2023-9-2 15:48:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
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)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-9-2 15:48:29 | 显示全部楼层
在你提供的代码中,有一个问题导致了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)

希望这次修改能够解决你的问题。如果还有其他疑问,请随时提问。
如果问题已经解决,请设置最佳答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-9-2 15:48:31 | 显示全部楼层
问题出在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)

希望能帮到你!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

也不对啊,修改后的代码和我发的一模一样啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

okok,没问题了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-9-3 17:13:11 | 显示全部楼层
当您使用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回答,如果胡说八道,请不要理会
如果对你有帮助,请设置一个最佳答案!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-25 00:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表