PHP-Programm für die längste palindromische Teilsequenz

Was ist Palindrom?

Ein Palindrom ist ein Wort, eine Phrase, eine Zahl oder eine Folge von Zeichen, die sich rückwärts wie vorwärts lesen lassen. Mit anderen Worten, es bleibt unverändert, wenn seine Zeichen umgekehrt werden.

Beispiel

• „Ebene“ ist ein Palindrom, weil es von links nach rechts und von rechts nach links gleich lautet.

• „Rennwagen“ ist ein Palindrom.

• „12321“ ist ein Palindrom.

• „Madam“ ist ein Palindrom.

PHP-Programm für die längste palindromische Folge

Sei X[0..n-1] die Eingabesequenz der Länge n und L(0, n-1) die Länge der längsten palindromischen Teilsequenz von X[0..n-1]. Wenn das letzte und das erste Zeichen von X gleich sind, dann ist L(0, n-1) = L(1, n-2) + 2. Sonst L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

Dynamische Programmierlösung

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

Ausgabe

The length of the longest palindromic subsequence is 7

Die Ausgabe des angegebenen Codes, wenn er mit der Eingabezeichenfolge „BBABCBCAB“ ausgeführt wird, ist Die Länge der längsten palindromischen Teilsequenz beträgt 7. Dies bedeutet, dass innerhalb der Eingabezeichenfolge „BBABCBCAB“ eine palindromische Teilsequenz der Länge 7 i vorhanden ist. e. BABCBAB. „BBBBB“ und „BBCBB“ sind ebenfalls palindromische Teilsequenzen der angegebenen Sequenz, jedoch nicht die längsten. Der Code berechnet diese Länge erfolgreich und gibt sie mithilfe dynamischer Programmierung zurück.

Fazit

Zusammenfassend lässt sich sagen, dass der bereitgestellte PHP-Code eine dynamische Programmierlösung implementiert, um die Länge der längsten palindromischen Teilsequenz in einer bestimmten Zeichenfolge zu ermitteln. Bei der Ausführung mit der Eingabezeichenfolge „BBABCBCAB“ wird korrekt ermittelt, dass die Länge der längsten palindromischen Teilsequenz 7 (BABCBAB) beträgt. Der Code stellt die Teilsequenz selbst jedoch nicht explizit bereit. Es funktioniert, indem es eine Tabelle mit Längen für verschiedene Teilzeichenfolgen erstellt und dabei Fälle berücksichtigt, in denen Zeichen übereinstimmen oder nicht übereinstimmen. Der Algorithmus berechnet die Länge effizient mithilfe eines Bottom-Up-Ansatzes, was zur gewünschten Ausgabe führt.

Das obige ist der detaillierte Inhalt vonPHP-Programm für die längste palindromische Teilsequenz. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!