<?php
function edit_distance_ond($str1 ,$str2){
$array = array();
$x = 0;
$y = 0;
$offset = strlen($str1);
$array[$offset + 1] = 0;
for($D = 0; $D <= strlen($str1) + strlen($str2); $D++){
//echo $D." ";
for($k = -$D; $k <= $D; $k += 2){
if($k == -$D || $k != $D && $array[$k-1+$offset] < $array[$k+1+$offset])
$x = $array[$k+1+$offset];
else
$x = $array[$k-1+$offset] + 1;
$y = $x - $k;
while($x < strlen($str1) && $y < strlen($str2) && $str1[$x] == $str2[$y]){
$x++;
$y++;
}
$array[$k+$offset] = $x;
if($x >= strlen($str1) && $y >= strlen($str2))
return $D;
}
}
return -1;
}
$a = "barcelona";
$b = "basrcelonaf";
$edo = edit_distance_ond($a,$b);
echo $edo;
?>
- Output for 4.3.0 - 4.3.11, 4.4.0 - 4.4.9, 5.0.0 - 5.0.5, 5.1.0 - 5.1.6, 5.2.0 - 5.2.17, 5.3.0 - 5.3.29, 5.4.0 - 5.4.45, 5.5.0 - 5.5.38, 5.6.0 - 5.6.40, 7.0.0 - 7.0.33, 7.1.0 - 7.1.33, 7.2.0 - 7.2.33, 7.3.0 - 7.3.33, 7.4.0 - 7.4.33, 8.0.0 - 8.0.30, 8.1.0 - 8.1.28, 8.2.0 - 8.2.18, 8.3.0 - 8.3.6
- 2
preferences:
274.37 ms | 405 KiB | 460 Q