Thank you, Gene.
Although I dont really understand perl language, I can figure out that
your code is about a top-down strategy with memoization. But I cannot
find the "b" table which is used for the common sequences storage,
maybe because of my inacquaintance with perl language.
Can you give me any hint?
Gene wrote:
> 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");
