Why does `re.search(r'(a+)+$', 'a'*30 + '!')` take exponential time?
answer
- Two quantifiers competing for the same characters
- Count the ways to carve up the run
- Compositions of n, two to the n minus one
- Failure must be proved, matching is guessed
- Search restarts at every offset
basics
~20 sThe inner a+ and the outer + can carve the run of as up in about 2^n ways. The trailing ! makes $ fail, so the backtracking engine must try every one of those splits before reporting no match.
solid answer
~40 s`re` is a backtracking engine: at every choice point it saves the untried alternative and comes back to it if the current path fails. In `(a+)+`, the inner `a+` may take any number of `a`s and the outer `+` repeats over what is left, so for `n` `a`s there are on the order of `2**(n-1)` distinct ways to partition the run — every one of them a saved state. Against `'a'*30 + '!'` the pattern consumes all the `a`s, `$` fails at the `!`, and the engine dutifully unwinds through the whole space before concluding failure. Each extra `a` roughly doubles the runtime. Crucially the cost is paid on **failure**: a string of pure `a`s matches on the first greedy attempt and returns instantly. `re.search()` then repeats that work from each starting offset.
code
python · 9 linesimport re
import time
pattern = re.compile(r"(a+)+$")
for n in (18, 20, 22):
subject = "a" * n + "!"
start = time.perf_counter()
pattern.search(subject)
print(n, round(time.perf_counter() - start, 3), "seconds")go deeper
Recall that the engine tries alternatives and undoes them, and that (a+)+ is the same thing as a+ written expensively. Being able to say 'it has to try every split' is enough at this level.
Expect to derive the count out loud: the inner and outer quantifiers can partition a run of n characters in roughly 2^(n-1) ways, and a failing tail forces all of them. Show the linear rewrite.
Demonstrate the doubling with a quick timing ladder and connect it to a real input shape — a near-match with one wrong character at the end. Explain why the test suite never saw it.
Frame the tradeoff: backtracking buys backreferences, lookaround and predictable match semantics, and the cost is unbounded worst-case time. Decide where that is acceptable and where input must never reach a regex.
## Backtracking, concretely CPython's `re` implements a pattern as a small program run by a backtracking matcher. Whenever the pattern reaches a point with two viable continuations — one more repetition of a quantifier, or stop repeating and continue with the rest of the pattern — the engine pushes the untried alternative onto a stack and takes one of them. If the rest of the pattern later fails, it pops the most recent alternative and resumes from there. The search finishes when some path succeeds, or when the stack is empty and every path has failed. ## Counting the paths in `(a+)+` Take the subject `aaaa`. The outer `+` runs the group one or more times; each run of the group consumes a non-empty run of `a`s via the inner `a+`. So a successful pass over `aaaa` corresponds to a way of writing 4 as an ordered sum of positive integers: `4`, `3+1`, `1+3`, `2+2`, `2+1+1`, `1+2+1`, `1+1+2`, `1+1+1+1`. Those are the **compositions** of 4, and there are `2**3 = 8` of them. In general a run of `n` characters has `2**(n-1)` compositions, and the engine can be made to walk all of them. Now append a character the pattern cannot accept. With `(a+)+$` and the subject `'a'*n + '!'`, the greedy first attempt swallows every `a`, then `$` is asked to match at the `!` and fails. The engine backtracks: give one `a` back to the outer repeat, re-split, try `$` again — still `!`, still fails. There is no arrangement of the `a`s that moves the `!`, so every one of the `2**(n-1)` splits is generated and rejected. Each extra `a` doubles the work. ## Why the failing input, and not the matching one A subject of pure `a`s matches on the very first greedy attempt and returns in microseconds. This asymmetry is the reason these bugs reach production: every happy-path test passes, and the killer input is a valid-looking string with one character wrong at the end — a missing closing bracket, a stray space, a truncated field. Test data almost never has that shape; user data has it constantly. ## `search` adds a factor `re.search()` does not try the pattern once; it tries it at offset 0, then offset 1, and so on until something matches or the string is exhausted. Each of those attempts pays its own backtracking cost, so an already-exponential per-offset cost is multiplied by the length of the string. `re.fullmatch()` and a leading `^` anchor remove that outer factor — which is a genuine mitigation, though it does nothing about the exponent itself. ## Why Python does not just avoid this A regular expression in the *formal* sense can be matched in time linear in the input by simulating an automaton, which never backtracks and never cares about ambiguity. Python's patterns are not formal regular expressions: backreferences (`(\w+) \1`), lookahead and lookbehind, and lazy quantifiers all exceed what such an automaton expresses, and the semantics of which alternative wins are defined in terms of a backtracking leftmost search. Keeping backtracking is what makes those features work and keeps match results predictable; the price is that ambiguous patterns can go exponential. ## Measuring it The doubling is easy to demonstrate and worth doing once by hand, because seeing 18, 20 and 22 characters take 0.013 s, 0.047 s and 0.187 s makes the shape of the curve obvious — and makes it obvious that a 40-character input is not a slightly slower version of the same thing but an unbounded hang. ## The fixes, in order of preference 1. **Remove the ambiguity.** `(a+)+$` means exactly what `a+$` means, and the rewrite is linear. `(\s*\w+)*` becomes `\w+(\s+\w+)*`. Make alternation branches disjoint so no two can match the same text. 2. **Anchor and bound.** Anchor with `^`/`re.fullmatch()` to kill the per-offset factor, and cap input length before matching. 3. **Forbid the backtracking.** Since 3.11, an atomic group `(?>...)` or a possessive quantifier such as `a*+` tells the engine to discard the saved alternatives, so there is nothing to unwind into. 4. **Stop using a regex.** A lot of these patterns are re-implementing `str.split()`, `str.partition()` or a real parser, and the non-regex version is both faster and readable.
- What is the equivalent pattern with no ambiguity, and does it change what matches?`a+$` accepts exactly the same set of strings as `(a+)+$` and runs in linear time. The rewrite only changes the group structure, so if you were capturing you lose the capture — and note that with `(a+)+` the group captures only the last repetition anyway, which is rarely what the author intended. Removing a pointless group is usually a readability win as well as a performance one.
- How much does anchoring the pattern with `re.fullmatch()` instead of `re.search()` help?It removes one factor of the input length, because `search` restarts the whole attempt at every offset while `fullmatch` tries only offset 0. That is a real improvement, but it is linear against an exponential term: a 40-character near-match still hangs. Anchoring is worth doing and is not a fix.
- Why does an automaton-based engine not have this problem, and why does `re` not use one?Simulating an automaton tracks all live alternatives at once, so it runs in time proportional to pattern size times input size regardless of ambiguity. It cannot express backreferences or lookaround, and it does not give Python's defined leftmost, greedy-first match semantics. `re` keeps backtracking to keep those features and that predictability.
saying these in an interview costs you the question
- Blames the length of the pattern rather than its ambiguity
- Thinks the matching input is the slow case
- Claims `re.compile()` removes the backtracking cost
- Says the engine is recursing and will raise RecursionError
- Believes anchoring alone makes the pattern safe
- Cannot name a linear rewrite of `(a+)+`