| Subject: | Use dynamic programming algorithm |
LCSS currently uses a O(n^3) algorithm. The dynamic programming
algorithm for this problem uses O(nm) in runtime and space (although the
later can easily reduced with perl. see
http://en.wikipedia.org/wiki/Longest_common_substring_problem).
A quick and dirty implementation:
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;
}
I've uploaded a C implementation as LCSS_XS.