String-Matching Automata

For a given pattern P, we can define its string-matching automata:

• (states)
• (start state)
• (accepting state)
• 

The transition function chooses the next state to maintain the invariant:

after scanning in the first i characters, the state number is the longest prefix of P that is also a suffix of .