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];
}
[download]

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;
[download]

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.