这是我在 ItoA 中看到的伪代码：
1 m = P.length
2 let pi[1...m] be a new array
3 pi[1] = 0
4 k=0
5 for q=2 to m
6 while k > 0 and P[k+1] != P[q]
7 k = pi[k]
8 if P[k+1] == P[q]
9 k = k+1
10 pi[q] = k
11 return pi
我的疑问是为什么在第 6 行我们这样做k = pi[k]而不是k--在我看来这应该是检查长度前缀的方式k（因为如果P[k+1] != P[q]这意味着k+1无法实现也是后缀的长度前缀）也可以是后缀，那与 相比P[q]，我也认为如果我们这样做，运行时间将保持不变。