On Mon, May 14, 2012 at 4:57 PM, Gabriel Z M Ramos
<gabriel@gargarullo.com> wrote:
It just looks odd that it can take over a minute to look for such a pattern in a 100 KB file if there's no match, whereas it will be "instantaneous" if there is one:
(("a"):rep(100000).."b"):find("a(.*)b")
All backtracking implementations of regular _expression_ searches tend to have this kind of worst-case behavior. Russ Cox has a nice writeup about the regular _expression_ matching (a series of 4 articles, probably more than you'd want to know):
