3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ perl.plover.com/NPC , hal.inria.fr/inria-00176043 $\endgroup$
    – Emil Jeřábek
    Jun 18, 2020 at 5:45
  • $\begingroup$ do you have a reference that defines the extended RegExp? Can't figure it out from your post. $\endgroup$
    – AmeerJ
    Jun 18, 2020 at 18:30
  • $\begingroup$ @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... $\endgroup$
    – Armin
    Jun 18, 2020 at 23:19

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.