From: Brian Candler <b.candler@...>
Date: 2012-03-15T06:28:22+09:00
Subject: Re: Problem replacing $datawith $data['abc'] using gsub

Bartosz Dziewoński wrote in post #1051341:
> This is a bad case of catastrophic backtracking -
> http://www.regular-expressions.info/catastrophic.html - and stems from
> the fact that matching a regex to a string is asymptotically
> exponential.

Well, matching a *real* regular expression to a string can be done in 
linear time by a DFA, with no backtracking. (However, it's true that the 
conversion of some pathological regexps into DFAs can take exponential 
resources)

The trouble is that "regexps" in programming languages seem to have 
grown features beyond true regular expressions.

-- 
Posted via http://www.ruby-forum.com/.