Определение наибольшей общей последовательности (LCS)

$a = 'hello moscow';
$b = 'exmos';

function lcs($s1,$s2) {
    $L1=mb_strlen($s1);
    $L2=mb_strlen($s2);
    $L=array();
    for($i=0;$i<=$L1;$i++) {
        $L[$i]=array();
        $L[$i]=array_fill(0,$L2,0);
    }
    for($i=$L1;$i>=0;$i--) {
        for($j=$L2;$j>=0;$j--) {
            if (($i==$L1) or ($j==$L2)) $L[$i][$j]=0;
            else if ($s1{$i}==$s2{$j}) $L[$i][$j]=1+$L[$i+1][$j+1];
            else $L[$i][$j]=max($L[$i+1][$j],$L[$i][$j+1]);
        }
    }
    // print LCS ( Longest Common Subsequence )
    $i=0;
    $j=0;
    $result='';

    while (($i < $L1) && ($j < $L2)) {
        if ($s1{$i}==$s2{$j}) {
            $result.=$s1{$i};
            $i++; $j++;
        }
        else if ($L[$i+1][$j] >= $L[$i][$j+1])
            $i++;
        else
            $j++;
    }
    echo "$result\n";

    // return LCS length
    return $L[0][0];
}

echo lcs($a,$b);