Search code examples
algorithmkmp

How to kmp algorithm deals with such error?

I get algorithm here

But what would be for another string for that algorithm with repeating pattern.

i.e. string:

a b c b b c b d a b c b d

pattern:

a b c b d

lps:

0 0 0 2 0

given mistmatch at j=4 i=4

next:

j=2 i=5 match (b)
j=3 i=6 match (c)
j=4 i=7 match (b)
j=5 i=8 match (d)

Patterm found which is wrong:

bbcbd!=abcbd

What is lps table wouldbe for an array?

Solution

  • You did not compute the KMP failure array (or prefix function) correctly. For each prefix p of the pattern, there is no proper suffix of p that is also a prefix of p; the failure array should be [0, 0, 0, 0, 0].