Here's a regex implementation that is polynomial in time and space: https://github.com/travisdowns/polyregex https://github.com/travisdowns/polyregex If you w

Here's a regex implementation that is polynomial in time and space: https://github.com/travisdowns/polyregex https://github.com/travisdowns/polyregex If you want to use extender regex that includes backreferences, it is still polynomial as long as the number of backreferences is fixed: since many regex syntaxes only support \1 through \9, the count is fixed by construction.