Hi Mathieu On Sat, Jul 22, 2006 at 01:12:33PM +0900, Mathieu Bouchard wrote: > This message is in MIME format. The first part should be readable text, > while the remaining parts are likely unreadable without MIME-aware tools. > On Thu, 20 Jul 2006, Reto Schuettel wrote: > > Actually, I found the answer: /foo/ acts like /^(?:.*)foo/, so /(.*)foo/ > acts like /^(?:.*)(.*)foo/, which is O(LENGTH^2) because the two > quantifiers don't talk to each other, and act as nested loops like: > > LENGTH.downto(0) {|n| > (LENGTH-n).downto(0) {|m| > try to match stuff and break when done > } > } > > To test my hypothesis, I tried /(.*)(.*)/ and it behaved like 3 nested > loops, in O(LENGTH^3). Hmm.. Makes sense! So the solution (pre_match) is actually causing this problem. :/. Thank you, I hope s.b. will be able to fix this. Regards, Reto Schuettel