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