Regex, compiled to a state machine.

Note

Thompson's construction builds the machine from pieces, one per operator. A literal is two states and an arrow. Alternation adds a state that forks into both branches with free moves, and another where they rejoin. Star adds a loop back over its body and a skip around it. Every piece has one way in and one way out, so they snap together, and the machine has at most two states per symbol of the pattern. This drawing merges the exit of one piece with the entry of the next instead of linking them with a free move, which saves a state per concatenation and changes nothing else.

To run it, start with the entry state plus everything reachable by free moves. For each character, follow every arrow labelled with it from every live state, then add the free moves again. The set can never hold more states than the machine has, so a string of length n against a pattern of length m costs on the order of n times m. The "state visits" counter adds up the size of the live set at each position.

Most regex engines in common use do something else. Perl, PCRE, Python, Java and JavaScript try one alternative, recurse, and back up on failure. On ordinary patterns that is fast. On (a*)*b against a run of a's with no b, every way of splitting the run between the inner and outer star is a separate path, and there are 2^n-1 of them. Twenty-five a's is already more than sixteen million. The NFA on this page handles the same input in 130 state visits. It never holds more than five states, and when the input runs out none of them is the accepting one.

Backtracking survives because it supports features an automaton cannot express, backreferences above all. Engines that refuse those features, such as Google's RE2, Go's regexp and Rust's regex crate, guarantee linear time. Cloudflare's global outage on 2 July 2019 came from a single firewall rule containing .*(?:.*=.*), which sent a backtracking engine into this kind of blow-up on every core at once.