KMP算法的next求不对

15588686105

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

1. def getnext(t):
   
2.     n = len(t)
   
3.     next = [0 for i in range(n)]
   
4.     j = 0  # i：前缀尾，j：后缀尾
   
5.     for i in range(1,n):
   
6.         while (t[i] != t[j]) and (j > 0):
   
7.             j = next[j - 1]
   
8.         if t[i] == t[j]:
   
9.             j += 1
   
10.         next[i] = j
    
11. 
    
12.     return next
    
13. 
    
14. t = input("输入子串：")
    
15. 
    
16. res = getnext(t)
    
17. 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,没问题了