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