Re: Common Substrings

and this may be the most efficient way to do it in perl:

sub common {
  my ($a, $b) = @_;
  my $min = 0;
  my $max = length $a < length $b ? length $a : length $b;
  
  while ($min < $max) {
    my $h = ($max - $min + 1) >> 1;
    my $c = substr($a, $min, $h);
    my $d = substr($b, $min, $h);
    if ($c eq $d) {
      $min += $h;
    }
    else {
      $max = $min + $h - 1;
    }
  }

  return (substr($a, 0, $min),
          substr($a, $min),
          substr($b, $min));
}
[download]

Comment on Re: Common Substrings Download Code

Replies are listed 'Best First'.
Re^2: Common Substrings by Anonymous Monk on Nov 15, 2005 at 11:19 UTC
Thanks! It took me a bit to understand that you were using a bisection method. But I agree that it should be reasonably efficient. I just have a tendency to avoid substr() since it always feels like a very expensive call. The strings that I am spliting are paths, and because my sub then looks for the place of a slash, which should be 8 bits, I think that it is safe for me to use a binary method.	[reply]
Re^3: Common Substrings by salva (Canon) on Nov 15, 2005 at 11:51 UTC
I just have a tendency to avoid substr() since it always feels like a very expensive call. `substr` is actually quite cheap as it doesn't copy the char data from the the original string, it just makes an alias to it. The strings that I am spliting are paths, and because my sub then looks for the place of a slash, which should be 8 bits I don't think so, on UTF8 strings byte offsets and char offsets can be different!	[reply] [d/l]