Deterministic-Finite-Automaton

Linear algorithm using a deterministic finite state automaton recognizing all string whose suffix is equal to the pattern. Construction of the automaton can be done in $O(m)$-time.

Appeared in:

• [31]: Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms (3. ed.). MIT Press (2009), http://mitpress.mit.edu/books/introduction-algorithms ↗