The
lcsbruteforce algorithm maintains this big table of solutions to subproblems. In this example, it's maintaining just the length of the LCS. Just change it to maintain the actual substring itself:
sub lcsbruteforce {
my($x, $y) = @_;
my(@v, $cx, $cy, $left, $above);
for my $xi (0 .. length($x) - 1) {
$cx = substr $x, $xi, 1;
for my $yi (0 .. length($y) - 1) {
$cy = substr $y, $yi, 1;
if ($cx eq $cy) {
# $v[$xi][$yi] = 1 + (($xi && $yi) ? $v[$xi - 1][$yi - 1] : 0);
$v[$xi][$yi] = ($xi && $yi ? $v[$xi-1][$yi-1] : "") . $cx;
} else {
# $left = ($xi && $v[$xi - 1][$yi]) || 0;
# $above = ($xi && $v[$xi][$yi - 1]) || 0;
# $v[$xi][$yi] = ($left > $above) ? $left : $above;
$left = ($xi && $v[$xi - 1][$yi]) || "";
$above = ($xi && $v[$xi][$yi - 1]) || "";
$v[$xi][$yi] = length($left) > length($above) ? $left : $above
+;
}
}
}
return $v[length($x) - 1][length($y) - 1];
}
To change it to an actual brute force algorithm? That would be pretty strange. The brute force algorithm is:
$best = "";
for every subsequence $s of $x:
if $s is also a subsequence of $y:
$best = $s if length($s) > length($best);
return $best;
Of course, the part where you get all subsequences and check for subsequence-ness is a pain. You can probably generate all subsequences using
Algorithm::Loops, and perhaps use some regex stuff to check whether a string was a subsequence of another.
-
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.