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

• "level" ist ein Palindrom, weil es von links nach rechts und von rechts nach links dasselbe liest.

• "racecar" ist ein Palindrom.

• "12321" ist ein Palindrom.

• "Madam" ist ein Palindrom.

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

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

 $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 

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 vorhanden ist ich .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.

Abschluss

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.