String-Matching Automata

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

• $Q = \{0,\dots,m\}$ (states)
• q₀ = 0 (start state)
• $A = \{m\}$ (accepting state)
• $\delta(q,a) = \sigma(P_q a)$

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

$\phi(T_i) = \sigma(T_i)$

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