Read your link carefully.  Real-world regular expression engines support backreferences, and efficiently determining whether an RE with backreferences matches a given string is an NP-complete problem.<p>If you&#x27;re going to implement this important feature in a sane way then at SOME point you&#x27;re going to need to backtrack.