I also went the route of creating a regular expression, and here is what I came up with. This RE most likely has abysmal exponential performance, as it backtracks extensively. It also does not work with duplicate elements in the input stream, as a (Perl) regular expression will be content with the leftmost match - had Perl a POSIX RE engine, that engine should match the longest match from what I remember...
Anyway, the code "simply" constructs a regular expression of one list that matches all possible subsequences in order, and then matches that list against the other list as a string. Spaces are used as the delimiters between the elements.
#!/usr/bin/perl -w
use strict;
use Test::More tests => 3;
sub lcos {
my ($list1,$list2) = @_;
my @list1 = @$list1;
my @list2 = @$list2;
# Assume that neither list1 nor list2 contain elements
# that stringify to the same value, that is, neither
# list1 nor list2 contain both "" and undef.
# Also, a blank is chosen as a delimiting character which
# shall appear in no element of list1 or list2
$list2 = " " . join(" ", @list2) . " ";
my $matcher = lcos_match(@list1);
#print $matcher,"\n";
my @result;
@result = split " ", $1
if $list2 =~ $matcher;
@result;
};
sub lcos_match {
my $match = '(';
while (@_) {
$match .= match_sequence(@_);
shift;
@_ and $match .= "|";
};
$match .= ')';
$match;
};
sub match_sequence {
my $result = "";
my $element;
while (defined ($element = pop)) {
$result = $result ? qr{ \Q$element\E$result?} : qr{ \Q$element\E }
+;
};
$result;
};
while (<DATA>) {
my ($l1,$l2,$expected) = split /\s*\|\s*/;
my @l1 = split /\s*/, $l1;
my @l2 = split /\s*/, $l2;
my @expected = split /\s*/, $expected;
$" = ",";
$, = ",";
is_deeply( [ lcos(\@l1,\@l2)], \@expected, "@l1 | @l2");
};
__DATA__
a b c d f g h j q z | a b c d e f g i j k r x y z | a b c d
a b c | a b x c | a b
a b c d | a b x b c d | b c d
| 