I'm studying KMP algorithm and I'm stuck on an example.

Suppose my text is "I am queen." and my pattern is "q".

The sp table will have only one value, q and it's sp index will be 0. Mismatch will occur at the very first index.

According to the formula: i - ( spi-1 + 1) ; the right shift will be 0.

And so the algorithm will get stuck and move nowhere.

What am I doing wrong?


The formula for shifting is i - spi + 1 if you start indexing from 0 and i - spi if you start indexing from 1.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.