Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
