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.

$\endgroup$
3
  • 2
    $\begingroup$ perl.plover.com/NPC , hal.inria.fr/inria-00176043 $\endgroup$ – Emil Jeřábek Jun 18 '20 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 '20 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 '20 at 23:19
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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