[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.

[ieviev]

It's still O(n * m). The matches are non-overlapping, even if you run a separate engine on the matches post-match it will at most traverse the full input once across all matches.

[mjmas]

Ture, I forgot about the non-overlapping matchss and that that will cancel out any extra n parameter.

Actually rereading again, it almost seems like it should be possible to do the matching as a special case of the Thompson/Pike VMs and have it loop back around to the start, and deduplicate multiples, but I am only speculating.