From: ts <decoux@...>
Date: 2002-04-04T02:11:14+09:00
Subject: Re: regular expression question

>>>>> "D" == David Alan Black <dblack@candle.superlink.net> writes:

>> Do you remember the well-known example NFA-vs-DFA with the P hack to solve
>> it ?

D> No, I don't know that one.

 Then try this regexp with your version of ruby

pigeon% time ruby -e '"bbbbXcXaaaaaaaaaaaaaaaaaaaaaaaa" =~ /.X(.+)+X/; p $&'
"bXcX"

real    0m0.019s
user    0m0.010s
sys     0m0.010s
pigeon% 

 and no pigeon is not a super-computer :-)

 To solve this problem the P regexp engine use a cache to remember the
 latest position where the regexp engine has failed, when it has detected a
 super-linear match.  

 This is why it's fast in this case


Guy Decoux