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

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

<?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
	// 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 = 'BBABCBCAB';
$n = strlen($seq);
echo "The length of the " .
	" longest palindromic subsequence is ", lps($seq);
?>

Sortie

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 i . 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é.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!