[algogeeks] Re: longest common subsequence problem

[Gene]

In perl (hopefully the homework has been due already)...

use strict;

our %memo;

sub lcs {
  my ($x, $y) = @_;

  my $key = "$x|$y";
  return $memo{$key} if defined $memo{$key};

  my $s = '';

  for (my $i = 0; $i < length($x); $i++) {
    for (my $j = 0; $j < length($y); $j++) {
      if (substr($x, $i, 1) eq substr($y, $j, 1)) {
        my $t = lcs(substr($x, 0, $i), substr($y, 0, $j))
              . substr($x, $i, 1)
              . lcs(substr($x, $i+1), substr($y, $j+1));
        $s = $t if length($t) > length($s);
      }
    }
  }
  $memo{$key} = $s;
  return $s;
}

print lcs("now is the time for all good men to come to the aid",
          "there are few good men who will aid women");