Finite Automaton Matching

Finite-automaton matching bakes the pattern into a small machine — a DFA (deterministic finite automaton) — and then matching is almost nothing: read the text once, follow exactly one arrow per character, and you have your answer. All the cleverness is moved into building the machine up front.

States = how much matched so far

For a pattern of length m, the DFA has m + 1 states, numbered by how many leading characters of the pattern have matched: state 0 means *nothing matched*, state m is the accept state — reaching it means the pattern just appeared. A precomputed transition table answers, for every state and every possible next character of the alphabet (Σ), which state to move to.

A worked DFA for ABA over {A, B}

state | meaning   |  A   |  B
------+-----------+------+-----
  0   | ""        |  1   |  0
  1   | "A"       |  1   |  2
  2   | "AB"      |  3   |  0
  3   | "ABA" ✓   |  1   |  2   <- accept

The forward arrows are obvious — state 2 on A advances to the accepting state 3. The subtle ones are the fall-backs. From state 1 ("A") reading another A stays at 1: the new A is itself a fresh one-character match. From the accept state 3, reading B goes to 2 because the text now ends in "AB", the longest pattern prefix that is still alive. Each transition lands on the longest pattern prefix that is a suffix of what was just read — the same prefix-suffix idea that powers KMP.

function automatonSearch(text, dfa, m) {
  let state = 0;
  const hits = [];
  for (let i = 0; i < text.length; i++) {
    state = dfa[state][text[i]];   // one lookup per character
    if (state === m) hits.push(i - m + 1);  // reached accept
  }
  return hits;
}

1. 1Build the transition table: for each state and each alphabet symbol, find the longest pattern prefix that is a suffix of the matched-text-plus-symbol.
2. 2Start the scan in state 0.
3. 3For each text character, look up the next state in the table — one constant-time step.
4. 4Whenever the scan enters the accept state, record a match ending here.