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