use strict;

my $replacecost = 2;
my $insertcost  = 1;
my $deletecost  = 1;

sub min(@) {
    my $minval = shift;
    my ($i, $j, $k);
    $j = 0; $k = 0;
    while ($i = shift) {
        $j++;
	if ($i < $minval) { $minval = $i; $k = $j; }
    }
    return ($minval, $k);
}

($#ARGV >= 1) or die "$0 target source\n";
my @target = split('', shift);
my @source = split('', shift);

my $n = @target; 
my $m = @source;
my @dist = ();
my @B = ();

$dist[0][0] = 0;

#for (my $i = 1; $i <= $n; $i++) { $dist[$i][0] = $i; $B[$i][0] = [$i-1,0]; }
#for (my $j = 1; $j <= $m; $j++) { $dist[0][$j] = $j; $B[0][$j] = [0,$j-1]; }

for (my $i = 1; $i <= $n; $i++) { 
    $dist[$i][0] = $dist[$i-1][0]+$insertcost; 
    $B[$i][0] = [$i-1,0];
}

for (my $j = 1; $j <= $m; $j++) { 
    $dist[0][$j] = $dist[0][$j-1]+$deletecost; 
    $B[0][$j] = [0,$j-1];
}

print <<EOA;
\\documentclass{article}
\\usepackage{tree-dvips}
\\begin{document}
\\begin{center}
EOA

print '{\footnotesize ' if ($n > 15);

print '\begin{tabular}{|cc|', 'c' x ($n+1), '|}', "\n";
print <<EOB;
\\hline
& \$i \\rightarrow\$
EOB

for (my $i = 0; $i <= $n; $i++) { print "& $i"; }

print <<EOC;
\\\\
\$\\\stackrel{j}{\\downarrow}\$ \&\&
EOC

for (my $i = 0; $i < $n; $i++) { print "& $target[$i] "; }

print '\\\\', "\n", '\hline', "\n", 
    '0 &', '& \node{0-0}{0$_{e}$} '; # (0,0)

for (my $i = 1; $i <= $n; $i++) { 
    print "& \\node{$i-0}{$dist[$i][0]\$_{i}\$} "; # (", $i-1, ",0)
}
print '\\\\', "\n";

for (my $j = 1; $j <= $m; $j++) {
    print "$j & $source[$j-1] & \\node{0-$j}{$dist[0][$j]\$_{d}\$}"; # (0,", $j-1, ")
    for (my $i = 1; $i <= $n; $i++) {
	my $add = ($source[$j-1] ne $target[$i-1]) ? $replacecost : 0;
	my $inscost = $insertcost + $dist[$i-1][$j];
	my $delcost = $deletecost + $dist[$i][$j-1];
	my $substcost = $add + $dist[$i-1][$j-1];
        my $k;
	($dist[$i][$j], $k) = min($substcost, $inscost, $delcost);
        print " & \\node{$i-$j}{$dist[$i][$j]\$_";
        if ($k == 0) {
	    $B[$i][$j] = [$i-1, $j-1];
	    if ($add == 0) { 
		print "{e}";  # (", $i-1, ",", $j-1, ")
	    } else {
		print "{s}";  # (", $i-1, ",", $j-1, ")
	    }
	}
        if ($k == 1) { 
	    $B[$i][$j] = [$i-1, $j];
	    print "{i}";      # (", $i-1, ",", $j, ")
	}
        if ($k == 2) { 
	    $B[$i][$j] = [$i, $j-1];
	    print "{d}";      # (", $i, ",", $j-1, ")
	}
        print '$}';
    }
    print '\\\\', "\n";
}
print '\hline', "\n";
print '\end{tabular}', "\n";

print ' }', "\n" if ($n > 15); # match the footnotesize command above

my $current = [$n,$m];
print "\\nodeoval{$n-$m}\n";
while (1) {
    my ($n, $m) = @{$current};
    last if (!defined $B[$n][$m]);
    my ($bn,$bm) = @{$B[$n][$m]};
    print "\\nodeoval{$bn-$bm}\n";
    if ($n == $bn) {
	print "\\anodecurve[r]{$n-$m}[r]{$bn-$bm}{10pt}\n";
    } else {
	print "\\anodecurve[l]{$n-$m}[r]{$bn-$bm}{10pt}\n";
    }
    $current = [$bn, $bm];
}

my $target = join('', @target);
my $source = join('', @source);
print <<EOZ;
\\par \\noindent Levenshtein distance between 
{\\em $target} and {\\em $source} \$=\$ $dist[$n][$m]
\\end{center}
\\end{document}
EOZ