I wondered about this for some time. Simple regex (as in formal language theory) are matched in O(n) time by finite automaton. Extended regex like PCRE are mo

I wondered about this for some time. Simple regex (as in formal language theory) are matched in O(n) time by finite automaton. Extended regex like PCRE are more powerful, but most of the time are implemented by backtracking engines, where really bad regex pattern might go exponential, but even simple pattern as in postmortem can go O(n^2). Do implementations optimize simple regex patterns to O(n) matching? Even I wrote x86 JIT regex compiler for fun some time ago. Compilation time was really bad, but matching was O(n).