321. How does string matching with a finite automaton work?
MediumString algorithms
Technical
Show model answer
Build a deterministic automaton with states 0..m, where state q means "the last q text characters match the first q pattern characters". For every state and every alphabet symbol, the transition gives the length of the longest pattern prefix that is a suffix of what has been read. Feeding the text through the automaton takes exactly one transition per character, so matching is O(n), and reaching state m signals an occurrence.
The cost is preprocessing: the transition table has (m + 1)·σ entries and can be built in O(mσ) using the KMP failure function. KMP can be seen as a compact version of this automaton that computes transitions on the fly using only O(m) space.