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