php中LCS函数遇到错误
-
20-12-2019 - |
题
我正在使用递归方法在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 的总长度,但给出“注意:未定义的偏移量:-1" 在打印函数中每次调用此行 echo $x[$i-1];
并且什么也不打印。我几乎尝试了所有方法来分割 $str1 的字符串,然后将其传递给函数,但没有任何效果。它不打印 LCS 字符串,因为这行代码有问题 echo $x[$i-1];
我无法得到。请帮忙。
笔记:上述代码的伪代码取自 Thomas H.Cormen,“算法导论第三版”。我将它写入 PHP 的目的是扩展它,以便它可以打印两个以上字符串的 LCS。如果有人分享如何扩展此代码的想法,以便它可以打印具有多个字符串(例如 $array{'sdsad','asddaw','asd',...n})的数组的 LCS,我将不胜感激。后来我打算把整个程序转成MATLAB。
解决方案 2
我已经解决了错误:我已经放置了 echo $x[$i-1];之前 lcs_print( $B, $x, $i = $i-1, $j = $j-1 );在 lcs_print 函数中,现在一切正常。
其他提示
您的 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 编写过代码,所以不能说语法。