# lcs.pl
use strict;
use Memoize;

sub longerOf {
    my ($x, $y) = @_;
    return (length $x > length $y) ? $x : $y;
}

memoize('lcs');
sub lcs {
    my ($a, $b) = @_;

    if ($a eq "" || $b eq ""){
        return "";
    }

    my ($az, $bz) = (chop $a, chop $b);
    if ($az eq $bz){
        return lcs($a, $b) . $az;
    } else {
        return longerOf(
                  lcs($a . $az, $b),
                  lcs($b . $bz, $a));
    }
}

while (1){
    print "1: "; my $a = <>; chomp $a;
    print "2: "; my $b = <>; chomp $b;
    print "LCS: ", lcs($a, $b), "\n\n";
}