[gbacon]

Without backreferences, it has a worst-case exponential blow up due to the DFA possibly needing to simulate that many simultaneous NFA states.

Regex matching with backreferences is NP-hard.

- https://perl.plover.com/NPC/NPC-3SAT.html

- https://perl.plover.com/NPC/NPC-3COL.html