Ошибка в функции LCS в php
-
20-12-2019 - |
Вопрос
Я кодирую LCS (самую длинную общую подпоследовательность) в программе php, используя рекурсивный подход.У меня есть следующий код:
<?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];
который я не могу получить.Пожалуйста помоги.
Примечание:Псевдокод приведенного выше кода был взят из книги Томаса Х.Кормен, «Введение в алгоритмы, 3-е издание».Я пишу его на PHP с намерением расширить его, чтобы он мог печатать LCS из более чем двух строк.Буду признателен, если кто-нибудь поделится идеей о том, как расширить этот код, чтобы он мог печатать LCS массива с несколькими строками, например $array{'sdsad','asddaw','asd',...n}.Позже я намерен преобразовать всю программу в 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, поэтому не могу сказать о синтаксисе.