Perl Regular Expression Matching is NP-Hard

Matching ordinary regular expresions can be done in polynomial time, proportional to MN, where M is the length of the regular expression and N is the length of the string to be matched. The usual method for this is: Parse the regular expression and construct an equivalent finite automaton (FA), which will have O(M) states; then simulate the action of the FA on the input, which takes O(MN) time. My Regex.pm module demonstrates this.

Source: Perl Regular Expression Matching is NP-Hard

Leave a Reply

Your email address will not be published. Required fields are marked *