PHPのLCS関数の直面誤差

Question

再帰的アプローチを使用して、PHPプログラムのLCS（最長共通のサブシーケンス）をコーディングしています。次のコードがあります。

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

.

LCSを印刷するには、次の関数を呼び出します。

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

.

このコードは、LCSの全長を正しくカウントしますが、印刷関数echo $x[$i-1];のこの行の呼び出しごとに「未定義のオフセット：-1」を表示し、何も印刷しません。私は$ str1の文字列を分割してから関数に渡すためにほとんどすべてを試しましたが、何も機能しませんでした。 LCS文字列は印刷されません。このコードのecho $x[$i-1];に問題があります。助けてください。

注：上記のコードの疑似コードは、Thomas H. Cormen、「アルゴリズム3RD版の紹介」の本から取られています。私はそれを拡張することを意図してそれを2つ以上の文字列のLCを印刷できるようにすることを意図しています。誰かがこのコードを拡張できるように、$ array {'sdsad'、 'asddaw'、 'asd'、... n}のような複数の文字列を持つ配列のLCSを印刷できるように、誰かがこのコードを拡張できるようにすることができます。その後、プログラム全体をMATLABに変換するつもりです。

Answer 1

私はエラーを解決しました：私はECHO $ X [$ i-1]を置きました。lcs_printの前に（$ b、$ x、$ i= $ i-1、$ j= $ j-1）。LCS_PRINT関数では、すべて元に問題があります。

Answer 2

あなたのlcs_lengthには問題があります。 1.（$ S1 [$ I-1]== $ S2 [$ J-1]）、IF（$ S1 [$ i]== $ S2 [$ J]）の場合はあったはずです。 2.Your境界条件（$ J= 0; $ J <$ N）は不明です、あなたはこの上書きを含める必要があります そして、あなたはそれを印刷しようとしています。このlcs_print（$ Backtracks、$ STR1、$ LEN1、$ LEN2）。 それは（$ j= 0; $ j <= n; $ J ++）

でした。

これらの変更は問題を解決すると思います。 私はPHPでコーディングしていませんので、構文については言えません。