Comment by mjmas

> no capture groups > [...] > no lazy quantifiers - .*?

Here's the caveats.

And so running a regex engine on the matches seems like it would get you back to O(regexlen * haystacklen * matchcount) or roughly O(mn²) again.