Are all RegExp solvable in O(n)? I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns ([abc]+);\1 would match abc;abc but not abc;cba, lazy or not greedy repetition operators [ab]+?ba$ would match abba or aaaabbbbba but not ababa.
I know that things like anchors (^ and $), optional operator (a?), character classes ([abc], or [^abc]) and the plus operator can be reduced to nominal regex operations or are simple checks in the end.
Thanks to @emil's comment and this stackoverflow answer, I now know that POSIX extended regular expressions are solvable in O(n) but backreferences are at least NP-hard and maybe NP-complete.