in reply to
Re^3: Longest Common SubSequence Not Working Correctly

in thread Longest Common SubSequence Not Working Correctly

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.