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
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|