sub lcss2 {
my ($s, $t) = @_;
my $z = 0;
my $m = length $s;
my $n = length $t;
my @S = (undef, split(//, $s));
my @T = (undef, split(//, $t));
my @L;
my @ret;
for my $i ( 1 .. $m ) {
for my $j ( 1 .. $n ) {
if ($S[$i] eq $T[$j]) {
$L[$i-1][$j-1] ||= 0;
$L[$i][$j] = $L[$i-1][$j-1] + 1;
if ($L[$i][$j] > $z) {
$z = $L[$i][$j];
@ret = ();
}
if ($L[$i][$j] == $z) {
push @ret,substr($s, ($i-$z), $z);
}
}
}
}
# warn Dumper \@L;
return join '*', @ret;
}
my $s1 = '6'x 200 . 'zyzxx';
my $s2 = '5'x 200 . 'abczyzefg';
my $count = 1;
timethese($count, {
'String::LCSS' => sub { String::LCSS::lcss( $s1, $s2 ) },
'dynprog' => sub { lcss2( $s1, $s2 )},
});
Update: Took the opportunity to learn XS and wrote String::LCSS_XS. |