alt Hacker News> 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.
> 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.
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.