Qu'est-ce que le palindrome ?

Un palindrome est un mot, une phrase, un nombre ou une séquence de caractères qui se lit de la même manière vers l'arrière et vers l'avant. Autrement dit, il reste inchangé lorsque ses caractères sont inversés.

Exemple

• "level" est un palindrome car il se lit de la même manière de gauche à droite et de droite à gauche.

• "voiture de course" est un palindrome.

• "12321" est un palindrome.

• "madame" est un palindrome.

Programme PHP pour la sous-séquence palindromique la plus longue

Soit X[0..n-1] la séquence d'entrée de longueur n et L(0, n-1) la longueur de la sous-séquence palindromique la plus longue de X[0..n-1]. Si le dernier et le premier caractères de X sont identiques, alors L(0, n-1) = L(1, n-2) 2. Sinon L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

Solution de programmation dynamique

 $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 

Sortir

The length of the longest palindromic subsequence is 7

La sortie du code donné, lorsqu'il est exécuté avec la chaîne d'entrée "BBABCBCAB", est La longueur de la sous-séquence palindromique la plus longue est 7. Cela signifie que dans la chaîne d'entrée "BBABCBCAB", il existe une sous-séquence palindromique de longueur 7. je .e. BABCBAB. BBBBB" et "BBCBB" sont également des sous-séquences palindromiques de la séquence donnée, mais pas les plus longues. Le code calcule et renvoie avec succès cette longueur en utilisant la programmation dynamique.

Conclusion

En conclusion, le code PHP fourni implémente une solution de programmation dynamique pour trouver la longueur de la sous-séquence palindromique la plus longue dans une chaîne donnée. Lorsqu'il est exécuté avec la chaîne d'entrée "BBABCBCAB", il détermine correctement que la longueur de la sous-séquence palindromique la plus longue est 7(BABCBAB). Cependant, le code ne fournit pas explicitement la sous-séquence elle-même. Il fonctionne en créant un tableau de longueurs pour différentes sous-chaînes, en considérant les cas où les caractères correspondent ou non. L'algorithme calcule efficacement la longueur en utilisant une approche ascendante, ce qui donne le résultat souhaité.