sub levenshtein($$){
  my @A=split //, lc shift;
  my @B=split //, lc shift;
  my @W=(0..@B);
  my ($i, $j, $cur, $next);
  for $i (0..$#A){
        $cur=$i+1;
        for $j (0..$#B){
                $next=min(
                        $W[$j+1]+1,
                        $cur+1,
                        ($A[$i] ne $B[$j])+$W[$j]
                );
                $W[$j]=$cur;
                $cur=$next;
        }
        $W[@B]=$next;
  }
  return $next;
}

sub min($$$){
  if ($_[0] < $_[2]){ pop @_; } else { shift @_; }
  return $_[0] < $_[1]? $_[0]:$_[1];
}

print levenshtein("gambol","gumbo");
print levenshtein("gumbo", "gambol");
print levenshtein("gumbo", "bumble");