#!/apps/bin/perl -w


# This program computes the edit distance between two strings


# computes the EDIT matrix

my $string1 = shift;

die "Where is the string?\n" unless defined($string1);


my $string2 = shift;

die "Where is the second string?\n" unless defined($string2);
 

print edit($string1,$string2);

# end Main

sub edit {

my @EDIT;
my @DECODING;
my $x = shift; # first string
my $y = shift; # scond string
my $m = length $x; # length of fisr string
my $n = length $y; # length of second string


# initialization

for($i=0; $i<= $m; $i++) {
    $EDIT[$i][0]=$i;
    $DECODING[$i][0]=0;
}
for($j=0; $j<= $n; $j++) {
    $EDIT[0][$j]=$j;
    $DECODING[0][$j]=1;
}  
# dynamic programming
for($i=1; $i<= $m; $i++) {

    for($j=1;$j<= $n; $j++) {
	@aux = ($EDIT[$i-1][$j]+1,
		$EDIT[$i][$j-1]+1, 
		$EDIT[$i-1][$j-1]+delta(substr($x,$i-1,1),substr($y,$j-1,1))
		);
	    $pos = where_min(@aux);
	$EDIT[$i][$j] = $aux[$pos];

	$DECODING[$i][$j] = $pos;
    }
}



# print decoding

$row = $m; 
$col = $n;
my @instructions = ();
while($row>=1 && $col>=1) {
  
    if($DECODING[$row][$col]==0) {
	$row=$row-1;
        $instruction = "delete ".substr($x,$row,1);
    } elsif($DECODING[$row][$col]==1) {
	$col=$col-1;
	$instruction = "insert ".substr($y,$col,1);
    } elsif($DECODING[$row][$col]==2) {
	$row=$row-1;
	$col=$col-1;
	if($EDIT[$row][$col]==$EDIT[$row+1][$col+1]) {
	    $instruction="no change";
	} else { $instruction = "change ".substr($x,$row,1)." by ".substr($y,$col,1); }

    } else { die "Invalid Code\n"; }

    push @instructions, $instruction;

}

foreach $e (reverse @instructions) {

    print "$e\n";
}
return $EDIT[$m][$n];

}

sub where_min {
    my @a = @_;
    my $l = $#a;
    my $i;
    my $min = 0;
    for($i=0;$i<=$l;$i++) {
       
	if($a[$min]>$a[$i]) { $min = $i; }
    }
    return $min;

}

sub min {
    my @a = @_;
    my $l = $#a;
    my $i;
    my $min = $a[0];
    for($i=0;$i<=$l;$i++) {
       
	if($min>$a[$i]) { $min = $a[$i]; }
    }
    return $min;
}

sub delta {
    my $a = shift;
    my $b = shift;
    return ($a eq $b ? 0 : 1);
    
    
}