Bad performance of simple regular expression - why??

[Joel C. Salomon]

Benji Smith wrote:
> The problem is that most regex engines (in fact, all of them, as far as 
> I know) use backtracking even when a DFA implementation could be used to 
> determine (much earlier in the search process) that a match is impossible.

This has been linked to in this thread, but Ken Thompson’s algorithm 
does /not/ use backtracking, and there are open-source implementations 
around; see <http://www.swtch.com/~rsc/regexp/regexp1.html>.

--Joel