All,
I am happily suprised with how efficient my attempt is. I whipped up a brute-force implementation and I am not sure when it will ever finish.
#!/usr/bin/perl
use strict;
use warnings;
my @str =
map {$_->[0]}
sort {$a->[1] <=> $b->[1]}
map {chomp; [$_, length($_)]} <DATA>;
print LCS(@str), "\n";
sub LCS {
my @str = @_;
my $next = combo(split //, $str[0]);
SUBSEQ:
while (my @subseq = $next->()) {
my $regex = join '.*', @subseq;
$regex = qr/$regex/;
for (1 .. $#str) {
next SUBSEQ if $str[$_] !~ /$regex/;
}
return join '', @subseq;
}
}
sub combo {
# modified [id://394168] to generate long to short
# - my ($by, $next) = (0, 1);
# + my ($by, $next) = ($#list + 2, 1);
# - $by++;
# - return () if $by > @list;
# + $by--;
# +return () if ! $by;
}
The pure regex brute-force solution by diotalevi is much better than this but still takes several minutes. Wow.
-
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.
|