Ok, first thing's first. What you actually want is the Largest Common Contiguous Ordered Subset. And so I give you a somewhat terrible algorithm (STA).
sub find_flccos {
my @a = @{$_[0]};
my @b = @{$_[1]};
my (%map,@curchk,@longest);
foreach my $i (0 .. $#a) {
# I decided to store this map so we don't repeat this
# O(n) step if we come across the same letter again
$map{$a[$i]} = [ grep $b[$_] eq $a[$i], (0 .. $#b) ] unless define
+d $map{$a[$i]};
# ok, these are the indices in b where we should
#start matching from
foreach my $j (@{$map{$a[$i]}}) {
@curchk = ();
# make temporary indices
my ($ti,$tj) = ($i,$j);
# fill @curchk with the longest current match
while ($ti < @a && $tj < @b && $a[$ti] eq $b[$tj]) {
push @curchk, $a[$ti];
$ti++;
$tj++;
}
# change the longest array if it is longer
#than the one found previously
@longest = @curchk if ($#curchk > $#longest);
}
}
return @longest;
}
__DATA__
my (@a,@b,@c,@d,@e,@f);
@a = qw( a a a a b c d );
@b = qw( a b c b a b a c a d );
@c = qw(fred bob joe jim mary elaine);
@d = qw(frank joe jim mary bob);
@e = @f = ();
print join ",", find_flccos(\@a,\@b);
print $/;
print join ",", find_flccos(\@d,\@c);
print $/;
print join ",", find_flccos(\@e,\@f);
print $/;
OUTPUT:
> perl flccos.pl
a,b,c
joe,jim,mary
>
Hope this helps.
Update: Looked like a disgusting mess before I put the comments on multiple lines. Sry ;-)
antirice
The first rule of Perl club is - use Perl
The ith rule of Perl club is - follow rule i - 1 for i > 1
-
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.