<?php

class StringDistance {
	public static function calculateDistance($string1,$string2) {
        $len1 = strlen($string1);
        $len2 = strlen($string2);
        $distanceArray = array_fill(0, $len1 + 1, array_fill(0, $len2 + 1, 0));
        
        for($i=1;$i<=$len1;$i++){
            $distanceArray[$i][0] = $i;
        }
        for($i=1;$i<=$len2;$i++){
            $distanceArray[0][$i] = $i;
        }
        
        for($i=1;$i<=$len1;$i++){
            for($j=1;$j<=$len2;$j++){
                
                $deletion = $distanceArray[$i-1][$j] + 1;
                $insertion = $distanceArray[$i][$j-1] + 1;
                $isMatched = $distanceArray[$i-1][$j-1] + (substr($string1, $i-1, 1) == substr($string2, $j-1, 1) ? 0 : 1);
                $swap = $len1 * $len2;
                if($i > 1 && $j > 1){
                    if(substr($string1, $i-1, 1) == substr($string2, $j-2, 1) 
                            && substr($string1, $i-2, 1) == substr($string2, $j-1, 1)
                        ){
                        $swap = $distanceArray[$i-2][$j-2] + 1;
                    }
                }
                //Log::write($i . " - " . $j . " = " . $deletion . "," . $insertion . "," . $isMatched . "(" . substr($string1, $i-1, 1) . "," . substr($string2, $j-1, 1) . ")" . "," . $swap);
                $distanceArray[$i][$j] = min($deletion, $insertion, $isMatched, $swap);
            }
        }
        //Log::write(print_r($distanceArray, true));
        
        return $distanceArray[$len1][$len2];
	}
	
	
}
?>