note
broquaint
<b>Update</b>: fixed code to work with [zby]'s case and hopefully any other case.<br/>
<b>Update</b>: code won't work with duplicates in the second list
<p/>
Not exactly vastly mystical but this should do the trick (although it hasn't been <i>thoroughly</i> tested)
<code>
use strict;
my @a = qw/ fred bob joe jim mary elaine /;
my @b = qw/ frank joe jim mary bob /;
print "LCS[anjiro] - ", join($", get_lcs(\@a, \@b)), $/;
@a = qw/ a b c /;
@b = qw/ a b x c /;
print "LCS[zby] - ", join($", get_lcs(\@a, \@b)), $/;
sub get_lcs {
my @a = @{ +shift };
my @b = @{ +shift };
my %map = map { $b[$_] => $_ } 0 .. $#b;
my(@lcs, @tmp);
for(0 .. $#a) {
next unless exists $map{$a[$_]}
or $a[$_ + 1] eq $b[$map{$a[$_]} + 1];
push @tmp, $a[$_] if $a[$_] eq $b[$map{$a[$_]}];
if($a[$_ + 1] ne $b[$map{$a[$_]} + 1]) {
@lcs = @tmp if @tmp > @lcs;
@tmp = ();
}
}
@lcs = @tmp if @tmp > @lcs;
return @lcs;
}
__output__
LCS[anjiro] - joe jim mary
LCS[zby] - a b
</code>
You might also find some roughly applicable questions under [Longest Common Substring].
<br/>
HTH
<p/>
<tt>_________<br><u>broquaint</u></tt>
263238
263238