Dada una secuencia, encuentre la longitud de la subsecuencia palindrómica más larga en ella.
Como otro ejemplo, si la secuencia dada es «BBABCBCAB», entonces la salida debería ser 7 ya que «BABCBAB» es la subsecuencia palindrómica más larga en ella. “BBBBB” y “BBCBB” también son subsecuencias palindrómicas de la secuencia dada, pero no las más largas.
1) Subestructura óptima:
Sea X[0..n-1] la secuencia de entrada de longitud n y L(0, n-1) la longitud de la subsecuencia palindrómica más larga de X[0..n-1].
Si el último y el primer carácter de X son iguales, entonces L(0, n-1) = L(1, n-2) + 2. De
lo contrario, L(0, n-1) = MAX (L(1, n-1 ), L(0, n-2)).
Lo que sigue es una solución recursiva general con todos los casos manejados.
Solución de programación dinámica
PHP
<?php
// A Dynamic Programming based
// PHP program for LPS problem
// Returns the length of the
// longest palindromic
// subsequence in seq
// A utility function to get
// max of two integers
// function max( $x, $y)
// { return ($x > $y)? $x : $y; }
// Returns the length of the
// longest palindromic
// subsequence in seq
function lps($str)
{
$n = strlen($str);
$i; $j; $cl;
// Create a table to store
// results of subproblems
$L[][] = array(array());
// Strings of length 1 are
// palindrome of length 1
for ($i = 0; $i < $n; $i++)
$L[$i][$i] = 1;
// Build the table. Note that
// the lower diagonal values
// of table are useless and
// not filled in the process.
// The values are filled in a
// manner similar to Matrix
// Chain Multiplication DP
// solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/).
// cl is length of substring
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];
}
// Driver Code
$seq = 'GEEKS FOR GEEKS';
$n = strlen($seq);
echo "The length of the " .
"LPS is ", lps($seq);
// This code is contributed
// by shiv_bhakt.
?>
The length of the LPS is 7
Consulte el artículo completo sobre la subsecuencia palindrómica más larga | DP-12 para más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA