Face à une erreur dans la fonction LCS en php

Question

Je code LCS (sous-séquence commune la plus longue) dans un programme php en utilisant une approche récursive.J'ai le code suivant:

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

Pour imprimer le LCS, j'appelle la fonction suivante :

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

Ce code compte correctement la longueur totale du LCS mais donne « Avis :Décalage non défini :-1" à chaque appel de cette ligne en fonction d'impression echo $x[$i-1]; et n'imprime rien.J'ai presque tout essayé pour diviser la chaîne de $str1 puis la transmettre à la fonction, mais rien ne fonctionne.Il n'imprime pas la chaîne LCS car quelque chose ne va pas avec cette ligne de code echo $x[$i-1]; que je n'arrive pas à obtenir.S'il vous plaît, aidez-moi.

Note:Le pseudocode du code ci-dessus est tiré du livre de Thomas H.Cormen, "Introduction aux algorithmes 3e édition".Je l'écris en PHP avec l'intention de l'étendre afin qu'il puisse imprimer des LCS de plus de deux chaînes.J'apprécierai si quelqu'un partage l'idée de Comment puis-je étendre ce code afin qu'il puisse imprimer le LCS d'un tableau avec plusieurs chaînes comme $array{'sdsad','asddaw','asd',...n}.Plus tard, j'ai l'intention de convertir l'intégralité du programme en MATLAB.

Answer 1

J'ai résolu l'erreur :J'ai placé echo $x[$i-1];avant lcs_print( $B, $x, $i = $i-1, $j = $j-1 );dans la fonction lcs_print, tout fonctionne bien maintenant.

Answer 2

Il y a des problèmes dans votre LCS_length
1.if ($s1[$i-1]==$s2[$j-1]), cela aurait dû être si ($s1[$i]==$s2[$j])
2.votre condition aux limites ($j=0 ;$ j <$ n) n'est pas clair, vous devez inclure cette haute telle et vous essayez de l'imprimer en appelant ce lcs_print ($ backtracks, $ str1, $ len1, $ len2).Cela aurait dû être ($j=0;$j<=n;$j++)

Je pense que ces changements résoudront le problème.Je n'ai pas fait de codage en PHP, je ne peux donc pas en dire plus sur les syntaxes.