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())
So at worst you have 2N scans of string 2, for O(N^2) total steps.
Andrew
