Program PHP untuk Urutan Palindromik Terpanjang

Apakah itu palindrom?

Palindrom ialah perkataan, frasa, nombor atau urutan aksara yang dibaca sama ke belakang dengan ke hadapan. Dalam erti kata lain, ia kekal tidak berubah apabila aksaranya diterbalikkan.

Contoh

• "level" ialah palindrom kerana bacaannya sama dari kiri ke kanan dan kanan ke kiri.

• "kereta lumba" ialah palindrom.

• "12321" ialah palindrom.

• "puan" ialah palindrom.

Program PHP untuk Urutan Palindromik Terpanjang

Misalkan X[0..n-1] ialah jujukan input bagi panjang n dan L(0, n-1) ialah panjang bagi turutan palindromik terpanjang bagi X[0..n-1]. Jika aksara terakhir dan pertama X adalah sama, maka L(0, n-1) = L(1, n-2) + 2. Lain L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

Penyelesaian Pengaturcaraan Dinamik

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

Keluaran kod yang diberikan, apabila dilaksanakan dengan rentetan input "BBABCBCAB", ialah Panjang jujukan palindromik terpanjang ialah 7 . Ini bermakna dalam rentetan input "BBABCBCAB", terdapat jujukan palindromik panjang 7 i . e. BABCBAB. BBBBB" dan "BBCBB" juga merupakan jujukan palindromik bagi jujukan yang diberikan, tetapi bukan urutan terpanjang. Kod ini berjaya mengira dan mengembalikan panjang ini menggunakan pengaturcaraan dinamik.

Kesimpulan

Kesimpulannya, kod PHP yang disediakan melaksanakan penyelesaian pengaturcaraan dinamik untuk mencari panjang urutan palindromik terpanjang dalam rentetan tertentu. Apabila dilaksanakan dengan rentetan input "BBABCBCAB", ia menentukan dengan betul bahawa panjang urutan palindromik terpanjang ialah 7(BABCBAB) Walau bagaimanapun, kod itu tidak memberikan urutan itu sendiri secara eksplisit. Ia berfungsi dengan membina jadual panjang untuk subrentetan yang berbeza, mempertimbangkan kes di mana aksara sepadan atau tidak sepadan. Algoritma cekap mengira panjang menggunakan pendekatan bawah ke atas, menghasilkan output yang diingini.

Atas ialah kandungan terperinci Program PHP untuk Urutan Palindromik Terpanjang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!