0

我正在使用递归方法在 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 的总长度，但在 print 函数中每次调用此行时都会给出“注意：未定义的偏移量：-1”echo $x[$i-1];并且什么也不打印。我已经尝试了几乎所有方法来拆分 $str1 的字符串，然后将其传递给函数，但没有任何效果。它不打印 LCS 字符串，因为这行代码有问题echo $x[$i-1];，我无法得到。请帮忙。

注意：上述代码的伪代码取自 Thomas H. Cormen 的书“Introduction to Algorithms 3rd Edition”。我正在将它写入 PHP 以扩展它，以便它可以打印两个以上字符串的 LCS。如果有人分享我如何扩展此代码的想法，以便它可以打印具有多个字符串（如 $array{'sdsad'、'asddaw'、'asd'、...n} ）的数组的 LCS，我将不胜感激。后来打算把整个程序转成MATLAB。

4

2 回答 2

0

我已经解决了错误：我已经放置了 echo $x[$i-1]; 之前 lcs_print($B, $x, $i = $i-1, $j = $j-1); 在 lcs_print 函数中，现在一切正常。

于 2014-04-13T22:13:57.303 回答
0

你的 LCS_length
1.if ($s1[$i-1]==$s2[$j-1]) 有问题，应该是 if ($s1[$i]==$s2[$j] )
2.你的边界条件 ($j=0; $j < $n) 不清楚，你需要包括这个上限并且你试图打印它调用这个 lcs_print($backTracks, $str1, $len1, $len2) . 应该是 ($j=0;$j<=n;$j++)

我认为这些改变将解决问题。我还没有用 PHP 编码，所以不能说语法。

于 2014-04-11T06:52:21.930 回答