Naive backtracking
The naive matcher tries a pattern against a text the way a person reading the pattern aloud might: take the next piece of the pattern, try to match it, and if everything after it also works out, you are done — otherwise go back and try a different choice at the last place one was available (a quantifier choosing to stop, or an alternation choosing a different branch). This is what a hand-written matcher, and many standard-library engines, implement by default — it is simple, and it is exactly as correct as the automaton pages, but it has no bound on how many times it might have to retry.
When it is the right choice
This is almost always fine: most patterns and most inputs give the matcher very little to backtrack over, and this is the algorithm behind back-references and lookaround, which the automaton pages cannot run at all. The danger is specific and well known: a quantified group nested inside another quantifier, asked to match an input that ultimately fails. Every way the outer quantifier could have split the input between its repetitions gets tried before the engine can conclude there is no match — and the number of ways to split n identical characters grows exponentially in n.
How it works
- Walk the pattern left to right, matching literal characters against the text directly.
- At a quantifier, try taking one more repetition first (greedy), and only fall back to stopping if everything after that repetition eventually fails.
- At an alternation, try each branch in the order it was written, taking the first one that leads to an eventual match.
- When a choice leads to failure, undo it — "backtrack" — and try the next available choice at the most recent decision point.
- The whole text matches if some sequence of choices lets the pattern and the text run out together.
Worth noticing
- The attempt count, not the step count, is the number to watch on this page. It is the direct answer to 'how much backtracking actually happened' — a path count, not a description of one.
- The ordinary and catastrophic scenarios use patterns and texts of comparable shape and length. The attempt count is still wildly different between them, which is the entire point: the blow-up comes from the pattern's structure, not from the length of anything.
- Every attempt this page draws is a real recursive call this algorithm actually makes — the tree is not illustrative, it is the literal shape of the computation, the same way `tools/recursion`'s naive Fibonacci tree is.
Cost
- Best
- O(n)
- Average
- O(n · m)
- Worst
- exponential in the input
- Extra space
- O(n + m) stack depth
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 page's own attempt count is bounded separately, by counting how many attempts a run would make before drawing a single one — an ordinary pattern and text pass easily, and a pattern shaped like the catastrophic example is refused outright once it would take more than a few thousand attempts to watch.