PHP Program for Longest Palindromic Subsequence

What is palindrome?

A palindrome is a word, phrase, number, or sequence of characters that reads the same backward as forward. In other words, it remains unchanged when its characters are reversed.

Example

• "level" is a palindrome because it reads the same from left to right and right to left.

• "racecar" is a palindrome.

• "12321" is a palindrome.

• "madam" is a palindrome.

PHP Program for Longest Palindromic Subsequence

Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic subsequence of X[0..n-1]. If last and first characters of X are same, then L(0, n-1) = L(1, n-2) + 2. Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

Dynamic Programming Solution

<?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);
?>

Output

The length of the longest palindromic subsequence is 7

The output of the given code, when executed with the input string "BBABCBCAB", is The length of the longest palindromic subsequence is 7 .This means that within the input string "BBABCBCAB", there exists a palindromic subsequence of length 7 i .e. BABCBAB. BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.The code successfully calculates and returns this length using dynamic programming.

Conclusion

In conclusion, the provided PHP code implements a dynamic programming solution to find the length of the longest palindromic subsequence in a given string. When executed with the input string "BBABCBCAB", it correctly determines that the length of the longest palindromic subsequence is 7(BABCBAB) However, the code does not explicitly provide the subsequence itself. It works by building a table of lengths for different substrings, considering cases where characters match or do not match. The algorithm efficiently calculates the length using a bottom-up approach, resulting in the desired output.

The above is the detailed content of PHP Program for Longest Palindromic Subsequence. For more information, please follow other related articles on the PHP Chinese website!