sub lcs {
  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);
      } else {
        $left = ($xi && $v[$xi - 1][$yi]) || 0;
        $above = ($xi && $v[$xi][$yi - 1]) || 0;
        $v[$xi][$yi] = ($left > $above) ? $left : $above; 
      }     
    }   
  } 
  return $v[length($x) - 1][length($y) - 1];
}