动态规划(最长公共子序列LCS)

``````<?php
class longest_common_subsequence
{
public function __construct(\$x, \$y, \$m, \$n, &\$c, &\$b)
{
for(\$i = 0; \$i <= \$m; \$i++)
{
\$c[\$i][0] = 0;
}
for(\$j = 1; \$j <= \$n; \$j++)
{
\$c[0][\$j] = 0;
}
for(\$i = 1; \$i<= \$m; \$i++)
{
for(\$j = 1; \$j <= \$n; \$j++)
{
if(\$x[\$i-1] == \$y[\$j-1])
{
\$c[\$i][\$j] = \$c[\$i-1][\$j-1] + 1;
\$b[\$i][\$j] = 0;
}
else if(\$c[\$i-1][\$j] >= \$c[\$i][\$j-1])
{
\$c[\$i][\$j] = \$c[\$i-1][\$j];
\$b[\$i][\$j] = 1;
}
else
{
\$c[\$i][\$j] = \$c[\$i][\$j-1];
\$b[\$i][\$j] = -1;
}
}
}
echo iconv('utf-8', 'gbk', "以上两个字符串的最长公共子序列为：\n");
\$this->output(\$b, \$x, \$m, \$n);
echo "\n";
}

private function output(\$b, \$x, \$i, \$j)
{
if(\$i == 0 || \$j == 0)
{
return;
}
if(\$b[\$i][\$j] == 0)
{
\$this->output(\$b, \$x, \$i-1, \$j-1);
echo \$x[\$i-1];
}
else if(\$b[\$i][\$j] == 1)
{
\$this->output(\$b, \$x, \$i-1, \$j);
}
else
{
\$this->output(\$b, \$x, \$i, \$j-1);
}
}
}

{
\$input = trim(fgets(STDIN));
return \$input;
}

function test()
{
\$x = 'ABCBDAB';
\$y = 'BDCABA';
\$b = array();
\$c = array();

\$m = strlen(\$x);
\$n = strlen(\$y);

new longest_common_subsequence(\$x, \$y, \$m, \$n, \$c, \$b);

return 0;
}

function main()
{
echo iconv('utf-8', 'gbk', "请输入第一个字符串：\n");
echo iconv('utf-8', 'gbk', "请输入第二个字符串：\n");
\$b = array();
\$c = array();

\$m = strlen(\$x);
\$n = strlen(\$y);

new longest_common_subsequence(\$x, \$y, \$m, \$n, \$c, \$b);

return 0;
}

if(!empty(\$argv[1]) && \$argv[1]=='test')
{
test();
}
else
{
main();
}``````

(=￣ω￣=)··· 暂无内容！

20

1

21

43