enter image description here

I know that in order to build i's failure link, I compare i's and j's success links:
If they are the same (if a = b), then i's failure link should point to state j + 1.
If they aren't the same, we go to the state pointed by j's failure link and do the same. (we stop when we fail at the initial state)
How do you compute the last state's "failure" link? For example if the pattern is "ABA": enter image description here

How do we compute that after we found a match, we should go to state 1? State 3 doesn't have a character it's expecting to see, so how do we do it?


1 Answer 1


The link for position $i$ is not determined by the letter at position $i$ but instead by the letter $b$ at position $i-1$ (and the failure link at $i-1$).

For the rest you correctly describe the algorithm: follow the failure links until we find a position $j$ such that the letter at that position equals $b$.

Usually the failure link at the last letter is not computed. The reason is that one does not need it: when we have reached the last position we have found the pattern! However, if we want to find the next match, a failure link at the end would be helpful.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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