String Matching: Computing the longest prefix suffix array in kmp algorithm
Following a case for which it does not work:
i 0 1 2 3 4 5
p A B A B B A
c1 0 0 1 2 0 1
c2 0 0 1 2 2 3
The reason being:
At i=4, len=2
p[i]='B' and p[len]='A' //Mismatch!
lps string upto i=3: AB(0-1 prefix), (2-3 suffix)
-------------------------------
i=4
Next charecter: B
len=2 // longest prefix suffix length
Charecter looking for : A (=p[len])
So upto i=3 we had AB(0-1) as the prefix that matched with suffix AB(2-3), but now at i=4 there is a mismatch so we see that we can't extend the original prefix(0-1) so the position to be checked is the prefix found prior to "AB" which is done by lps[len-1] < -1 as the array starts from 0 > and this is not necessarily len-1 as we may need to step back further than that to get the new longest prefix suffix.