Skip to interview prep
Apexed

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.

How does string matching with a finite automaton work — Data structures & algorithms interview question — Apexed