KMP Preprocessing Function

Question

this is the pseudo code I've see in 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

my doubt is why on line 6 we do k = pi[k] instead of k-- which seems to me that should be the way of checking a preffix of length k (because if P[k+1] != P[q] it means that a preffix of lenght k+1 that's also suffix cannot be achieved) which can be also suffix, that is comparing with P[q], I also think that if we do it, the running time will stay the same.

Answer 1

The recursive call k = pi[k] searches for the smaller border of p[1..q]; because the pi[k], which is the largest border of P[0..k], is smaller border of p[1..q] than pi[q]. It will search until it finds a border of p[1..q] where the next character p[k+1] is not equal to P[q+1].

You can find more details here: http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm