Backtrack Bomb

One innocent regex, one evil string — watch catastrophic backtracking detonate, then go linear.

How to read this lab

The exact same pattern is matched by two real, from-scratch regex engines against a growing string of the same repeated character. One engine's work explodes exponentially as the string grows by even one character; the other stays almost perfectly flat.

Controls

Preset: Catastrophic uses (a+)+b — the classic nested-quantifier pattern; Benign uses a+b for comparison.
Length n (all 'a', no trailing match): How many 'a' characters are in the test string — never a trailing match, so both engines have to fully search and fail.
Jump to max length: Snaps straight to the longest length the demo allows.

What to watch for

On the Catastrophic preset, drag Length n up one step at a time and watch Backtracking steps roughly quadruple with each +2 characters.
Linear (NFA) steps barely moves for the same input — it grows proportionally to length, not exponentially.
Switch to the Benign preset — both engines now stay flat, since there's no ambiguity left for the backtracker to re-explore.

Why it happens

(a+)+b lets the same run of 'a' characters be split between the inner and outer + in exponentially many equivalent ways. When the overall match ultimately fails (no trailing 'b'), the backtracking matcher has to try every one of those splits before giving up — a real, unavoidable cost of how naive backtracking explores ambiguous repetition. The linear matcher sidesteps this entirely by tracking the whole SET of possible positions at once instead of trying them one at a time with backtracking — exactly the fix real engines like RE2 and Rust's regex crate use to guarantee this can never happen.

Try this first — Drag Length n from 10 to 18 on the Catastrophic preset and watch Backtracking steps and the Blow-up ratio.

Climbing fast — 398x more backtracking steps than linear

At n=12, the backtracking matcher already needs 28,670 steps against the linear matcher's 72 — and this pattern's nested quantifiers mean every extra character roughly doubles the backtracking count. Drag the length slider up to watch it tip into full collapse.

Backtracking steps (log scale)
Linear (NFA) steps (log scale)
Blow-up zone

Seed1

Seed is decorative here — every step count is a deterministic function of the pattern and input, not randomness. Reseeding only nudges the marker’s pulse animation.

Pattern

Preset

(a+)+b — nested quantifiers create exponentially many equivalent ways to split the same run of characters.

Evil string

Length n (all 'a', no trailing match)12 chars

Capped at 20 chars — the backtracking matcher already performs millions of steps here; longer strings would stall the browser tab.

Backtracking steps

28,670

Recursive match-attempts for n=12

Linear (NFA) steps

State-set advances, same input

Blow-up ratio

398.2x

Backtracking steps / linear steps