The only reason some regular expression engines take exponential time to match strings is because those implementations don't use regular expressions at all. Fe

The only reason some regular expression engines take exponential time to match strings is because those implementations don't use regular expressions at all. Features like backreferences break them out of that class of languages. When you take the "regular" bit seriously you can guarantee linear time matching. See the engines used in Rust and Go.