O que é palíndromo?

Um palíndromo é uma palavra, frase, número ou sequência de caracteres que é lida da mesma forma de trás para frente. Em outras palavras, permanece inalterado quando seus caracteres são invertidos.

Exemplo

• "level" é um palíndromo porque é lido da mesma forma da esquerda para a direita e da direita para a esquerda.

• "carro de corrida" é um palíndromo.

• "12321" é um palíndromo.

• "madame" é um palíndromo.

Programa PHP para a maior subsequência palindrômica

Seja X[0..n-1] a sequência de entrada de comprimento n e L(0, n-1) seja o comprimento da subsequência palindrômica mais longa de X[0..n-1]. Se o último e o primeiro caracteres de X forem iguais, então L(0, n-1) = L(1, n-2) 2. Caso contrário, L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

Solução de programação 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 

Saída

The length of the longest palindromic subsequence is 7

A saída do código fornecido, quando executado com a string de entrada "BBABCBCAB", é O comprimento da subsequência palindrômica mais longa é 7. Isso significa que dentro da string de entrada "BBABCBCAB", existe uma subsequência palindrômica de comprimento 7 eu.e. BABCBAB. BBBBB” e “BBCBB” também são subsequências palindrômicas da sequência fornecida, mas não as mais longas. O código calcula e retorna com sucesso esse comprimento usando programação dinâmica.

Conclusão

Concluindo, o código PHP fornecido implementa uma solução de programação dinâmica para encontrar o comprimento da subsequência palindrômica mais longa em uma determinada string. Quando executado com a string de entrada "BBABCBCAB", ele determina corretamente que o comprimento da subsequência palindrômica mais longa é 7(BABCBAB). No entanto, o código não fornece explicitamente a subsequência em si. Funciona construindo uma tabela de comprimentos para diferentes substrings, considerando casos em que os caracteres correspondem ou não. O algoritmo calcula eficientemente o comprimento usando uma abordagem bottom-up, resultando na saída desejada.