Regular expressions

Thompson's construction (NFA)

Thompson's construction turns a parsed pattern into a nondeterministic finite automaton (an NFA) by composing a small, fixed wiring diagram per operator — concatenation chains two fragments, alternation forks and rejoins them, each quantifier adds a loop or a bypass. Simulating it does not try one possibility and back out of it if it fails; instead it tracks the whole *set* of states the automaton could be in, and advances every one of them together on each input character.

When it is the right choice

This is the shape of engine behind every regex implementation that promises linear-time matching regardless of the pattern — RE2 and Rust's `regex` crate both work this way, specifically to make catastrophic backtracking structurally impossible rather than merely unlikely. The cost is expressiveness: back-references and lookaround cannot be compiled to a finite automaton at all, which is why those engines refuse them outright rather than silently falling back to something slower.

How it works

• Build the automaton once from the pattern, by Thompson's construction.
• Start in the epsilon closure of the start state — every state reachable without consuming a character.
• For each input character, move every currently active state along a transition that matches it, then take the epsilon closure of wherever that lands.
• Repeat until the input is exhausted.
• The whole input matched if, and only if, the accepting state is among the states active at the end.

Worth noticing

• The active-states picture is often more than one node at once. That is not the automaton being indecisive — it genuinely does not yet know which path the input will confirm, and it is cheaper to track all of them than to guess and be wrong.
• The number of active states never exceeds the number of states in the automaton, however long the input runs. That bound is the entire reason this algorithm cannot blow up the way backtracking can.
• Every character is looked at exactly once. Scrub back and forth and count: the step counter advances by exactly one per character, never more, whatever the pattern looks like.

Cost

Best

O(n · m)

Average

O(n · m)

Worst

O(n · m)

Extra space

O(m)

The pattern is capped at 14 characters and the text at 24, both pedagogical rather than technical: every extra pattern character can roughly double the automaton this tool draws, and this tool draws one frame per character, so the real limit in practice is legibility rather than time.

Worth comparing

• Subset construction (DFA) — The same automaton, pre-expanded so there is only ever one active state instead of a set — the determinism this page computes at run time, done once at build time instead.
• Naive backtracking — What this page is the alternative to: the same question, answered by trying one path at a time and undoing it on failure, which is where the cost this page avoids comes from.

All regex algorithms