<?php
function snake($k,$y,$str1,$str2){
$x = $y - $k;
while($x < count($str1) && $y < count($str2) && $str1[$x] == $str2[$y]){
$x++;
$y++;
}
return $y;
}
function edit_distance_onp($str1, $str2){
$s1 = count($str1) > count($str2) ? $str2 : $str1;
$s2 = count($str1) > count($str2) ? $str1 : $str2;
$fp = array();
$x = 0;
$y = 0;
$k = 0;
$p = 0;
$offset = count($s1) + 1;
$delta = count($s2) - count($s1);
for ($i = 0; $i < 15; $i++)
$fp[$i] = -1;
for ($p = 0; $fp[$delta + $offset] != count($s2); $p++) {
for($k = -$p; $k < $delta; $k++)
$fp[$k + $offset] = snake($k, max($fp[$k-1+$offset] + 1, $fp[$k+1+$offset]), $s1, $s2);
for($k = $delta + $p; $k > $delta; $k--)
$fp[$k + $offset] = snake($k, max($fp[$k-1+$offset] + 1, $fp[$k+1+$offset]), $s1, $s2);
$fp[$delta + $offset] = snake($delta, max($fp[$delta-1+$offset] + 1, $fp[$delta+1+$offset]), $s1, $s2);
}
return $delta + ($p - 1) * 2;
}
$cha1[0] = "aaa";
$cha1[1] = "bbb";
$cha1[2] = "ccc";
$cha2[0] = "ddd";
$cha2[1] = "bbb";
$cha2[2] = "fff";
echo edit_distance_onp($cha1,$cha2);
?>
- 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.24 - 5.5.35, 5.6.7 - 5.6.28, 7.0.0 - 7.0.20, 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
- 4
preferences:
266.42 ms | 406 KiB | 344 Q