[Previously published here.]

Russ Cox recently wrote an article about the worst-case run time of two different implementation strategies for matching regexes: Thompson NFA, and backtracking NFA. In particular, Russ points to the Perl regex engine as an example of how not to do it.

The article’s an interesting read. But I don’t think the approach described is necessarily easy and/or useful to fit into Perl, though.