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

• Jun 18 '20 at 5:45
• do you have a reference that defines the extended RegExp? Can't figure it out from your post. Jun 18 '20 at 18:30
• @AmeerJ the combination of Emil's comment and this stackoverflow.com/a/13356328/1950267 already answers my question pretty much. I've found the stackoverflow link while looking for a specification of extended RegExp... Jun 18 '20 at 23:19