3 ms·
Even though this implementation is short, don't think it is efficient. Matching regular expressions can be done in linear time. This presented algorithm takes
by albertzeyer 15y ago
Even though this implementation is short, don't think it is efficient.
Matching regular expressions can be done in linear time.
This presented algorithm takes exponential time.
- berntb 15y agoMy "point" was a joke about PCRE, the present regexp engine in Python and most other open source languages. The answer I got (in addition to a couple of good introductory lectures I should send to people :-) ) seems to be that is sucks. :-(
- nandemo 15y ago> Matching regular expressions can be done in linear time. Unfortunately, the expression "regular expression" has been so abused in the context of programming that, unless otherwise specified, we cannot expect it to correspond to the well-defined regular expression that is used in formal language theory. For example, statements such as "you can use regular expressions to parse HTML" and "regexps aren't regular" (mentioned in this thread) are now acceptable. I wish people would at least say "extended regular expressions", but it's a lost cause.