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