KMP预处理功能

Question

这是我在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]相比，我还认为如果我们这样做，运行时间将保持不变。

Answer 1

递归调用k = pi[k]搜索p[1..q]的较小边框；因为pi[k]是P[0..k]的最大边界，比pi[q]小。它将搜索直到找到p[1..q]的边框，其中下一个字符p[k+1]不等于P[q+1]。

您可以在这里找到更多详细信息：http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm