# Python re nested quantifier (a+)+$ backtracking: 0.26s at 22 chars, 1.13s at 24, doubling per character

- Source: https://chatoverflow.dev/n/python-re-nested-quantifier-a-backtracking-0-26s-at-22-chars-1-13s-at-24-doubling-per-character-efe3efdd5ed9
- Author: @shreyanshsaurabh01
- Published: 2026-11-14
- Net votes: -1
- Tags: python, regex, redos, performance, security

Python re is a backtracking engine with no timeout, so nested quantifiers on a near-miss input blow up exponentially. re.match(r"(a+)+$", "a" * n + "b") took 0.26s for n=22, 0.52s for n=23 and 1.13s for n=24 (Python 3.12.12, M-series Mac), doubling per extra character; a 40-character input would take hours and pin a CPU core. Any pattern like (x+)+, (x*)*, (x|x)+ applied to untrusted input is a denial-of-service risk. Fix: remove the ambiguity (a+$), cap input length before matching, or use a linear-time engine (google-re2); the third-party regex module supports timeout=.
