Error de enfrentamiento en la función LCS en php

Question

Estoy codificando LCS (subsecuencia común más larga) en un programa php utilizando un enfoque recursivo.Tengo el siguiente código:

<?php

$lcsTbl = array(array(128),array(128));
$backTracks = array(array(128),array(128));

$str1 = 'asdvadsdad'; 
$str2 = 'asdasdadasda';

$len1 = strlen($str1);
$len2 = strlen($str2); 

echo LCS_Length($lcsTbl, $backTracks, $str1, $str2, $len1, $len2); //longest common sub sequence

echo '<br/>';

function LCS_Length(&$LCS_Length_Table, &$B, &$s1, &$s2, &$m, &$n)
{
  //reset the 2 cols in the table
  for($i=1; $i < $m; $i++) $LCS_Length_Table[$i][0]=0;
  for($j=0; $j < $n; $j++) $LCS_Length_Table[0][$j]=0;

  for ($i=1; $i <= $m; $i++) {
    for ($j=1; $j <= $n; $j++) {
      if ($s1[$i-1]==$s2[$j-1])
        { $LCS_Length_Table[$i][$j] = $LCS_Length_Table[$i-1][$j-1] + 1; $B[$i][$j] = '\\';}
      else if ($LCS_Length_Table[$i-1][$j] >= $LCS_Length_Table[$i][$j-1])
        { $LCS_Length_Table[$i][$j] = $LCS_Length_Table[$i-1][$j];  $B[$i][$j] = '|';}
      else
        { $LCS_Length_Table[$i][$j] = $LCS_Length_Table[$i][$j-1]; $B[$i][$j] = '-';}
    }
  }

  return $LCS_Length_Table[$m][$n];
}

Para imprimir el LCS, llamo a la siguiente función:

$x = str_split($str1);
echo lcs_print($backTracks, $str1, $len1, $len2); //print longest common sub sequence


function lcs_print(&$B, &$x, &$i, &$j)
{
    if( $i == 0 || $j == 0 )
        return;
    if( $B[$i][$j] == '\\' ) {
        echo $x[$i-1];
        lcs_print( $B, $x, $i = $i-1, $j = $j-1 );


    } else if( $B[$i][$j] == '|' ) {
        lcs_print( $B, $x, $i = $i-1, $j );
    } else {
        lcs_print( $B, $x, $i, $j = $j-1 );
    }
}
?> 

Este código cuenta correctamente la longitud total de LCS pero muestra "Aviso:Desplazamiento indefinido:-1" en cada llamada de esta línea en la función de impresión echo $x[$i-1]; y no imprime nada.He intentado casi todo para dividir la cadena de $str1 y luego pasarla a funcionar, pero nada funciona.No imprime la cadena LCS porque hay algún problema con esta línea de código echo $x[$i-1]; que no puedo conseguir.Por favor ayuda.

Nota:El pseudocódigo del código anterior ha sido tomado del libro de Thomas H.Cormen, "Introducción a los algoritmos, tercera edición".Lo estoy escribiendo en PHP con la intención de extenderlo para que pueda imprimir LCS de más de dos cadenas.Apreciaría si alguien comparte una idea de cómo puedo extender este código para que pueda imprimir LCS de una matriz con múltiples cadenas como $array{'sdsad','asddaw','asd',...n}.Posteriormente tengo la intención de convertir todo el programa a MATLAB.

Answer 1

He solucionado el error:He colocado echo $x[$i-1];antes de lcs_print( $B, $x, $i = $i-1, $j = $j-1 );en la función lcs_print, todo está funcionando bien ahora.

Answer 2

Hay problemas en tu LCS_length
1.si ($s1[$i-1]==$s2[$j-1]), debería haber sido si ($s1[$i]==$s2[$j])
2.su condición de contorno ($j=0;$j < $n) no está claro, debe incluir este límite superior y estás intentando imprimirlo llamando a esto lcs_print($backTracks, $str1, $len1, $len2).Debería haber sido ($j=0;$j<=n;$j++)

Creo que estos cambios resolverán el problema.No he codificado en PHP, así que no puedo opinar sobre las sintaxis.