面对PHP中LCS函数的错误

Question

I am coding LCS(longest common subsequence) in php program by using recursive approach. I have the following code:

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

To print the LCS, I call the following function:

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

This code counts the total lengthof LCS correctly but gives "Notice: Undefined offset: -1" on every call of this line in print function echo $x[$i-1]; and prints nothing. I have tried almost everything to split the string of $str1 and then pass it to function, but nothing works. It does not print LCS string because something is wrong with this line of code echo $x[$i-1]; which I am unable to get. Please help.

Note: The pseudocode of the above code has been taken from book of Thomas H. Cormen, "Introduction to Algorithms 3rd Edition". I am writing it into PHP with the intention of extending it so that it can print LCS of more than two strings. I'll appreciate if anyone shares idea of How can I extend this code so that it can print LCS of an array with multiple strings like $array{'sdsad','asddaw','asd',...n}. Later, I intend to convert the entire program into MATLAB.

Answer 1

I have solved the error: I have placed echo $x[$i-1]; before lcs_print( $B, $x, $i = $i-1, $j = $j-1 ); in lcs_print function, all is working fine now.