lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

2009/12/27 David Manura <>:
> On Sat, Dec 26, 2009 at 12:29 PM, David Manura wrote:
> ('a'):rep(5000):match'a*b'   -- fails slowly (about a second)
> BTW, s:match'a*b' is equivalent to s:match'^.-(a*b)'.

I think I'm getting a feel for the kind of ambiguity (or looseness)
that causes a lot of backtracking. As a human pattern-matcher, I would
notice that there is no 'b' in the pattern, so wouldn't bother
beginning again at the second character. But a computer is not human!

Reversing the string can speed things up (excuse my less compressed notation):

(('a'):rep(5000)..'caaaab'):match'a*b' -- finds 'aaaab' slowly

local s = ('a'):rep(5000)..'caaaab'
local s1 = string.reverse(s)
print(string.reverse(string.match(s1, "ba*")) -- finds 'aaaab' quickly