[issue44699] Simple regex appears to take exponential time in length of input

[Matthew Barnett]

Matthew Barnett <python at mrabarnett.plus.com> added the comment:

It's called "catastrophic backtracking". Think of the number of ways it could match, say, 4 characters: 4, 3+1, 2+2, 2+1+1, 1+3, 1+2+1, 1+1+2, 1+1+1+1. Now try 5 characters...

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue44699>
_______________________________________