KMP Algorithm Example

Question

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 - ( sp_i-1 + 1) ; the right shift will be 0.

And so the algorithm will get stuck and move nowhere.

What am I doing wrong?

Answer 1

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