¿Qué es palíndromo?

Un palíndromo es una palabra, frase, número o secuencia de caracteres que se lee igual hacia atrás que hacia adelante. En otras palabras, permanece sin cambios cuando se invierten sus caracteres.

Ejemplo

• "nivel" es un palíndromo porque se lee igual de izquierda a derecha y de derecha a izquierda.

• "coche de carreras" es un palíndromo.

• "12321" es un palíndromo.

• "señora" es un palíndromo.

Programa PHP para la subsecuencia palindrómica más larga

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)).

Solución de programación dinámica

 $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 

Producción

The length of the longest palindromic subsequence is 7

La salida del código dado, cuando se ejecuta con la cadena de entrada "BBABCBCAB", es La longitud de la subsecuencia palindrómica más larga es 7. Esto significa que dentro de la cadena de entrada "BBABCBCAB", existe una subsecuencia palindrómica de longitud 7. es decir. BABCBAB. BBBBB” y “BBCBB” también son subsecuencias palindrómicas de la secuencia dada, pero no las más largas. El código calcula y devuelve con éxito esta longitud mediante programación dinámica.

Conclusión

En conclusión, el código PHP proporcionado implementa una solución de programación dinámica para encontrar la longitud de la subsecuencia palindrómica más larga en una cadena determinada. Cuando se ejecuta con la cadena de entrada "BBABCBCAB", determina correctamente que la longitud de la subsecuencia palindrómica más larga es 7 (BABCBAB). Sin embargo, el código no proporciona explícitamente la subsecuencia en sí. Funciona construyendo una tabla de longitudes para diferentes subcadenas, considerando casos en los que los caracteres coinciden o no. El algoritmo calcula eficientemente la longitud utilizando un enfoque ascendente, lo que da como resultado el resultado deseado.