これは、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--kP[k+1] != P[q]k+1P[q]