# The last failure link in KMP automaton 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": 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

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.