> 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.
Matching regular expressions can be done in linear time.
This presented algorithm takes exponential time.