Download the raw code.
#
# longest common substring
#
my @str1 = $*IN.get.comb;
my @str2 = $*IN.get.comb;
my %table;
my $length = 0;
my $result = '';
for ^@str1 X ^@str2 -> $i, $j {
if @str1[$i] eq @str2[$j] {
%table{$i}{$j} = 1 + ( %table{$i-1}{$j-1} // 0);
if %table{$i}{$j} >= $length {
$length = %table{$i}{$j};
$result = [~] @str1[ $i-$length+1 .. $i];
}
}
}
say $result;
A short and sweet solution. It doesn't get more surveyable than this.
I can't say I care much for the practice of putting space after the opening paren or bracket, but not before the closing one. A very minor nit, though.
Interestingly, this is a case where the names @str1
and @str2
are
perfectly acceptable. There's nothing to distinguish the two strings
apart from them being first and second.
I think we need a module in Perl 6 to let people do array indexing on strings. People seem to really want it. And it would make this short program a few tokens shorter, even.
Two questions arise about %table
: why is it a hash of hashes, when all
its indexes are a (non-sparse) rectangle of integers? And why not go for
a descriptive name, like length
or common-length
?
The %table
variable helps propagate a bit of the information, saving
us a third loop. But this algorithm is still pretty slow.
How could I fail to mention the X
operator in the for
loop? A very
appropriate use of it, I think.
As usual, you can count on fox for making every line of code count.