Here is my stab at it. (LCCOS takes the reference to two array for input and spit back a reference to an array)
use strict;
use warnings;
use Data::Dumper;
my @array1 = qw(l a r g e s t
c o m m o n s e q u e n c i
a l s u b s e t
);
my @array2 = qw(w h a t i s t
h e l a r g e s t s e q u e
n c i a l
);
my @array3 = qw(w h a t l a r
g s e q c o m m o n
);
my @array4 = qw(w h a t l a r
g s e q c o m m o n s e q u e
n c i a l
);
my @array5 = qw( a b c d e f g h i j
k l m n o p q r s t u v w x y z
);
my @array6 = qw( a b c X f g h X l m
n X j k a b c d
);
print Dumper LCCOS(\@array1,\@array2);
print Dumper LCCOS(\@array2,\@array3);
print Dumper LCCOS(\@array3,\@array1);
print Dumper LCCOS(\@array1,\@array1);
print Dumper LCCOS(\@array2,\@array4);
print Dumper LCCOS(\@array5,\@array6);
####################################
sub LCCOS {
####################################
my ($array1,$array2) = @_;
my $current_largest = [];
my $current_size;
if ( @$array1 > @$array2 ) {
($array1,$array2) = ($array2,$array1)
};
my $count = 0;
my %elements_in_longer;
#create an HoA holding the locations of all elements
#in the larger array so we only start at those places
push @{$elements_in_longer{$_}},
$count++ for @$array1;
for my $pos_in_small ( 0 .. $#array2 ) {
my $current_letter = $array2->[$pos_in_small];
for my $possible_start(@{$elements_in_longer{$current_letter}}) {
my $curr_pos_in_small = $pos_in_small;
my $curr_pos_in_large = $possible_start;
my @curr_matching_sequence;
while ( defined $array1->[$curr_pos_in_large]
and
defined $array2->[$curr_pos_in_small] ) {
if ($array1->[$curr_pos_in_large]
eq
$array2->[$curr_pos_in_small]) {
push @curr_matching_sequence,
$array2->[$curr_pos_in_small];
$curr_pos_in_large++;
$curr_pos_in_small++;
} else { last; }
}
if ( @curr_matching_sequence > @{$current_largest} ) {
$current_largest = \@curr_matching_sequence;
$current_size = @curr_matching_sequence;
}
}
#if the $current_size is longer that what is left to
#check in the smaller array, then we are done.
last if $current_size > $#array2 - $pos_in_small;
}
return $current_largest;
} ##LCCOS
-enlil