On Feb 14, Andrew Pimlott said:
>On Thu, Feb 14, 2002 at 10:20:50PM -0500, Jeff 'japhy' Pinyan wrote:
>> while ($str =~ m{ ([^\0]{$len,}) (?= [^\0]* \0 [^\0]*? \1 ) }xg) {
>
>Thanks to the comma, ^
>
>> $len = length($match = $1) + 1;
>> }
>
>this is O(N^3) in the case of no common substring:
>
>- 1 factor for the positions at which the re engine tries to match
>- 1 factor for the lengths it tries for {$len,}
>- 1 factor for scanning string 2, failing to find \1
>
>I think that without the comma there is no O(N^3) worst case. For
>every scan of string 2, you either
>
>- find \1, in which case the re engine stops and you increment $len
>- don't find \1, in which case it increments $+[0] (aka pos())
Except that you are forced to find a 2-character match, which means you
end up skipping a POTENTIAL 3-character-or-more match.
--
Jeff "japhy" Pinyan [EMAIL PROTECTED] http://www.pobox.com/~japhy/
RPI Acacia brother #734 http://www.perlmonks.org/ http://www.cpan.org/
** Look for "Regular Expressions in Perl" published by Manning, in 2002 **
<stu> what does y/// stand for? <tenderpuss> why, yansliterate of course.
[ I'm looking for programming work. If you like my work, let me know. ]
