
$one = <>;
$two = <>;
chomp $one;
chomp $two;
$match = 5;
$gap = -2;

$len1 = length $one;
$len2 = length $two;

$T[0][0] = 0;

# leftmost column
for ($i = 1; $i <= $len1; $i++)
{
   $T[$i][0] = $T[$i-1][0] + $gap;
}

# top row
for ($j = 1; $j <= $len2; $j++)
{
   $T[0][$j] = $T[0][$j-1] + $gap;
}

# succeeding rows
for($i = 1; $i <= $len1; $i++)
{
   for($j = 1; $j <= $len2; $j++)
   {
      $left = $T[$i][$j-1] + $gap;
      $top = $T[$i-1][$j] + $gap;
      $win = $left > $top ? $left : $top; # $win = maximum($left,$top)
      if ((substr $one,$i-1,1) eq (substr $two,$j-1,1))
      {
         $diag = $T[$i-1][$j-1] + $match;
         $win = $win > $diag ? $win : $diag; # $win = maximum($win,$diag)
      }
      $T[$i][$j] = $win;
   }
}

# remove #'s if you want to print table
#for($i = 0; $i <= $len1; $i++)
#{
#  for($j = 0; $j <= $len2; $j++)
#  {
#     printf "%4d", $T[$i][$j];
#  }
#  print "\n";
#}

print "score: ", $T[$len1][$len2], "\n";
