PHP 最长回文子序列程序
phpserver side programmingprogramming更新于 2025/8/29 10:22:17
什么是回文?
回文是指正读和倒读相同的单词、短语、数字或字符序列。换句话说，即使字符反转，它的内容也保持不变。
示例
"level"是回文，因为它从左到右和从右到左读起来都一样。
"racecar"是回文。
"12321"是回文。
"madam"是回文。
求最长回文子序列的 PHP 程序
设 X[0..n-1] 为长度为 n 的输入序列，L(0, n-1) 为 X[0..n-1] 的最长回文子序列的长度。 如果 X 的首尾字符相同，则 L(0, n-1) = L(1, n-2) + 2。 否则 L(0, n-1) = MAX (L(1, n-1), L(0, n-2))。
动态规划解决方案
<?php
// 基于动态规划的
// 解决 LPS 问题的 PHP 程序
// 返回 seq 中最长回文子序列的长度
//
// 一个实用函数，用于获取
// 两个整数中的最大值
// function max( $x, $y)
// { return ($x > $y)? $x : $y; }
// 返回 seq 中最长回文子序列的长度
// 函数 lps($str)
{
$n = strlen($str);
$i; $j; $cl;
// 创建一个表来存储
// 子问题的结果
$L[][] = array(array());
// 长度为 1 的字符串是
// 长度为 1 的回文
for ($i = 0; $i < $n; $i++)
$L[$i][$i] = 1;
// 构建表格。注意:
// 表格下对角线的值
// 是无用的，
// 不会在过程中填充。
// 这些值的填充方式
// 类似于矩阵
// 链式乘法 DP
// cl 是子字符串的长度
for ($cl = 2; $cl <= $n; $cl++)
{
for ($i = 0; $i < $n - $cl + 1; $i++)
{
$j = $i + $cl - 1;
if ($str[$i] == $str[$j] &&
$cl == 2)
$L[$i][$j] = 2;
else if ($str[$i] == $str[$j])
$L[$i][$j] = $L[$i + 1][$j - 1] + 2;
else
$L[$i][$j] = max($L[$i][$j - 1],
$L[$i + 1][$j]);
}
}
return $L[0][$n - 1];
}
// 驱动代码
$seq = 'BBABCBCAB';
$n = strlen($seq);
echo "The length of the " .
" longest palindromic subsequence is ", lps($seq);
?>
输出
The length of the longest palindromic subsequence is 7
当使用输入字符串"BBABCBCAB"执行给定代码时，其输出为最长回文子序列的长度为 7。这意味着在输入字符串"BBABCBCAB"中，存在一个长度为 7 的回文子序列，即 BABCBAB。 "BBBBB" 和 "BBCBB" 也是给定序列的回文子序列，但不是最长的。代码使用动态规划成功计算并返回了该长度。
结论
总之，提供的 PHP 代码实现了一个动态规划解决方案，用于查找给定字符串中最长回文子序列的长度。当使用输入字符串"BBABCBCAB"执行时，它正确地确定了最长回文子序列的长度为 7(BABCBAB)。然而，代码并没有明确提供子序列本身。它的工作原理是构建一个包含不同子字符串长度的表格，同时考虑字符匹配或不匹配的情况。该算法使用自下而上的方法高效地计算长度，并得到所需的输出。
