I wonder how gracefully redgrep handles this. This tool hasn't been talked about since the year of its release. If I recall correctly, it doesn't handle some obstruse regexes the way conventional tools do however.
I have not verified it but i assume matching the whole line grep-style would bypass this problem entirely
Since a regex with ^<pattern>$ can not have overlapping matches it should guarantee linearity, given a linear engine. Or in the case of preprocessing lines first and then running is_match it's also linear
https://github.com/google/redgrep