Errore di fronte nella funzione LCS in PHP

Question

Io sto codificando LCS (successive comuni più lunghe) nel programma PHP utilizzando approccio ricorsivo. Ho il seguente codice:

<?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];
}

.

Per stampare il LCS, chiamo la seguente funzione:

$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 );
    }
}
?> 

.

Questo codice conta correttamente il totale del LungeLof LCS ma dà "Avviso: Offset indefinito: -1" su ogni chiamata di questa linea in funzione di stampa echo $x[$i-1]; e stampa nulla. Ho provato quasi tutto per dividere la stringa di $ STR1 e poi passarlo per funzionare, ma nulla funziona. Non stampare la stringa LCS perché qualcosa non va in questa linea di codice echo $x[$i-1]; che non riesco a ottenere. Per favore aiuto.

Nota: la pseudocodice del codice sopra è stata prelevata dal libro di Thomas H. Cormen, "Introduzione all'algoritmo 3rd Edition". Lo scrivo in PHP con l'intenzione di estenderlo in modo che possa stampare LC di più di due stringhe. Apprezzerò se qualcuno condivide un'idea di come posso estendere questo codice in modo che possa stampare LCS di un array con più stringhe come $ array {'sdsad', 'asddaw', 'asd', ... n}. Più tardi, intendo convertire l'intero programma in Matlab.

Answer 1

Ho risolto l'errore: Ho inserito Echo $ X [$ I-1];Prima di LCS_Print ($ B, $ X, $ i= $ I-1, $ J= $ J-1);Nella funzione LCS_Print, tutto funziona bene ora.

Answer 2

Ci sono problemi nella tua LCS_Length
1.Se ($ S1 [$ i-1]== $ s2 [$ j-1]), avrebbe dovuto essere se ($ s1 [$ i]== $ s2 [$ j])
2. La tua condizione del contorno ($ j= 0; $ j <$ n) non è chiaro, è necessario includere questo in alto E stai cercando di stampare chiamando questo LCS_Print ($ backtracks, $ STR1, $ LEN1, $ LEN2). Avrebbe dovuto essere ($ j= 0; $ j <= n; $ j ++)

Penso che queste modifiche risolranno il problema. Non ho finito la codifica in PHP, quindi non posso dire sulle sintassi.