So verwenden Sie die Palindrome-Funktion in Java – Methoden und Beispiele

Du weißt, was ein Palindrom ist, oder?

Ein Palindrom ist eine Phrase oder ein Satz, der vorwärts und rückwärts dasselbe liest, wie zum Beispiel „Madam, ich bin Adam“ oder „verdammt, ich bin verrückt“ oder „ein Mann, ein Plan, ein Kanal, Panama“.

Schnelle Navigation
Längster palindromischer TeilstringManachers Algorithmus und Palindromfunktion in JavaBeispiele für Palindromfunktionen in JavaManachers Algorithmus: Ein typisches BeispielEinige abschließende Gedanken zur Palindromfunktion in Java

Längster palindromischer Teilstring

Die Informatik befasst sich mit dem Konzept von längster palindromischer Teilstringoder längster Symmetriefaktor. Dies ist das Problem, den längsten Teilstring eines Strings zu finden, der sich auch als Palindrom liest.

Betrachten Sie das Wort „Bananen“ – das „Anana“ davon ist ein Palindrom. Im Wort „Abrakadabra“ ist das gesamte Wort kein Palindrom, aber „aca“ und „ada“ innerhalb dieses Wortes sind palindromisch. Bei diesem Ansatz ist es manchmal notwendig, alle palindromischen Teilzeichenfolgen zu betrachten, die für sich allein stehen und nicht erweitert oder mit anderen, längeren palindromischen Teilzeichenfolgen verbunden werden können.

In den 70er Jahren entwickelte Glenn Manacher einen Algorithmus und ein Regelwerk für Palindrome, die am Anfang einer bestimmten Zeichenfolge erscheinen. Spätere Forscher fanden heraus, dass derselbe Algorithmus verwendet werden kann, um alle palindromischen Teilzeichenfolgen irgendwo in der ursprünglichen Eingabezeichenfolge zu bestimmen (beides sind lineare Zeitlösungen).

Manachers Algorithmus
Und Palindrom-Funktion in Java

Dieser Algorithmus kann als eine Reihe von Grundregeln für Beobachtungen und Merkmale eines Palindroms und Subpalindroms betrachtet werden:

• Bei der Betrachtung der Palindromfunktion in Java muss die linke Seite eines Palindroms das Spiegelbild der rechten Seite sein
• Ein drittes Palindrom, das sich auf der rechten Seite eines ersten Palindroms befindet, hat genau die gleiche Länge wie ein zweites Palindrom, das in der Mitte auf der linken Seite positioniert ist. Das heißt, wenn das zweite Palindrom noch um ein Zeichen innerhalb der Grenzen des ersten Palindroms liegt oder nicht bis zur linken Grenze des ersten Palindroms reicht
• Wenn ein zweites Palindrom auf die linke Grenze des ersten Palindroms trifft oder darüber hinausgeht, sollte der Abstand von der Mitte des zweiten Palindroms zur linken Grenze des ersten genau gleich dem Abstand von der Mitte des dritten Palindroms zur Mitte des ersten Palindroms sein rechts gebunden
• In einem Beispiel wie dem obigen kann die Länge des dritten Palindroms als nächstes Zeichen nach dem Zeichen an der rechten Grenze des ersten Palindroms bestimmt werden. Es kann dann mit seinem Spiegelcharakter im Zentrum des dritten Palindroms verglichen werden
• Wenn bei der Bestimmung der palindromischen Länge eines vierten Palindroms dessen Mittelpunkt außerhalb der rechten Grenze des ersten Palindroms liegt, kann weder das erste noch das zweite Palindrom zur Bestimmung dieser Länge verwendet werden
• Bei der Bestimmung der palindromischen Länge einer Teilzeichenfolge kann man sich das erste Palindrom als Referenz mit den am weitesten rechts stehenden Zeichen in einer Zeichenfolge vorstellen

Beispiele für Palindromfunktionen in Java

Nehmen wir an, dass s eine Zeichenfolge mit N Zeichen ist. In diesem Fall kann s2 als abgeleitete Folge von s mit N * 2 + 1 Elementen betrachtet werden.

Jedes Element sollte einem oder mehreren der folgenden Elemente entsprechen:

• Die N Zeichen in s
• Die N-1-Grenzen zwischen diesen Zeichen
• Alle Grenzen vor oder nach dem ersten und letzten Zeichen

Eine Grenze in s2 kann als gleich jeder anderen Grenze in s2 betrachtet werden, wenn es darum geht, Elemente abzugleichen und die palindromische Länge zu bestimmen. Für das Array der palindromischen Spanne für die Elemente in s2, von der Mitte bis zu einer der äußersten Grenzen, sollte jede Grenze zur palindromischen Länge gezählt werden.

Mit anderen Worten: Ein Palindrom mit einer Palindromspanne von 1 wäre drei Elemente lang. Dies würde in unserem Beispiel als p dargestellt werden.

Die Position des Zentrums des Palindroms, das eine Grenze enthält, die der rechten Grenze von s2 am nächsten liegt, wird in unserem Beispiel durch c dargestellt, also p*2+1. Die Position der rechten Grenze dieses Palindroms wird durch r dargestellt, dh r = c+p. Für die Position eines Zeichens oder einer Grenze in s2 mit einer palindromischen Spanne, die noch bestimmt werden muss, sollte diese in unserem Beispiel durch i dargestellt werden, wobei i immer rechts von c steht. i2 ist also die gespiegelte Position von i um c, also {i, i2} = {6,4}, {7,3}, {8,2}, wenn c = 5

Manachers Algorithmus: Ein typisches Beispiel

verkohlen[] s2 = addBoundaries(s.toCharArray());

int[] p = neu int[s2.length];

int c = 0, r = 0; // Hier wurde das erste Element in s2 verarbeitet.

int m = 0, n = 0; // Die Wanderindizes zum Vergleich, ob zwei Elemente gleich sind

für (int i = 1; i

Wenn (i>r) {

P[i] = 0; m = i-1; n = i+1;

} anders {

int i2 = c*2-i;

Wenn (P[i2]<(ri-1)) {

P[i] = S[i2];

m = -1; // Dies signalisiert die Umgehung der while-Schleife unten.

} anders {

P[i] = ri;

n = r+1; m = i*2-n;

}

}

während (m>=0 && n

P[i]++; M–; n++;

}

Wenn ((i+p[i])>r) {

c = i; r = i+p[i];

}

}

int len ​​= 0; c = 0;

für (int i = 1; i

Wenn (len

len = p[i]; c = i;

}

}

verkohlen[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);

zurückkehren String.valueOf(removeBoundaries(ss));

}

Privat
statisch verkohlen[] addBoundaries(char[] cs) {

Wenn (cs==Null || cs.length==0)

zurückkehren „||“.toCharArray();

verkohlen[] cs2 = neu verkohlen[cs.length*2+1];

für (int i = 0; i<(cs2.length-1); i = i+2) {

cs2[i] = ‚|‘;

cs2[i+1] = cs[i/2];

}

cs2[cs2.length-1] = ‚|‘;

zurückkehren cs2;

}

Privat
statisch verkohlen[] removeBoundaries(char[] cs) {

Wenn (cs==Null || cs.length<3)

zurückkehren „“.toCharArray();

verkohlen[] cs2 = neu verkohlen[(cs.length-1)/2];

für (int i = 0; i

cs2[i] = cs[i*2+1];

}

zurückkehren cs2;

}

}

Bestimmen, ob ein String ein Palindrom ist

In diesen Fällen kann jedes Zeichen in einer Schleife durchlaufen und mit dem Zeichen auf der gegenüberliegenden Seite verglichen werden. Das Problem bei diesem Ansatz besteht darin, dass die Hälfte der Arbeit unnötig ist, da jedes Zeichen zweimal überprüft wird.

Im englischen Palindrom „Madam“ würde der Algorithmus jeden Buchstaben als Zeichen prüfen, während eigentlich nur die ersten beiden Zeichen und die letzten beiden Zeichen verglichen werden müssten – das mittlere müsste nicht überprüft werden.

Mit Rekursion nach Palindrom-Strings suchen (Mit freundlicher Genehmigung des Anfängerbuchs)

Paket beginnersbook.com;

import java.util.Scanner;

Klasse PalindromeCheck

{

//Meine Methode zur Überprüfung

öffentlicher statischer boolescher Wert isPal(String s)

{ // Wenn die Länge 0 oder 1 ist, ist String ein Palindrom

if(s.length() == 0 || s.length() == 1)

return true;

if(s.charAt(0) == s.charAt(s.length()-1))

/* auf erstes und letztes Zeichen von String prüfen:

* Wenn sie gleich sind, machen Sie dasselbe für einen Teilstring

* mit entferntem ersten und letzten Zeichen. und mach weiter so

* bis Ihre Zeichenfolge abgeschlossen ist oder die Bedingung fehlschlägt

* Funktion, die sich selbst aufruft: Rekursion

*/

return isPal(s.substring(1, s.length()-1));

/* Wenn die Programmsteuerung diese Anweisung erreicht, bedeutet dies

* Der String ist kein Palindrom und gibt daher „false“ zurück.

*/

falsch zurückgeben;

}

public static void main(String[]args)

{

//Zum Erfassen von Benutzereingaben

Scanner scanner = neuer Scanner(System.in);

System.out.println(„Geben Sie die Zeichenfolge zur Überprüfung ein:“);

String string = scanner.nextLine();

/* Wenn die Funktion „true“ zurückgibt, dann ist die Zeichenfolge

* Palindrom, sonst nicht

*/

if(isPal(string))

System.out.println(string + “ ist ein Palindrom“);

anders

System.out.println(string + “ ist kein Palindrom“);

}

}

Ausgabe 1:

Geben Sie die Zeichenfolge zur Überprüfung ein:

qqaabb

qqaabb ist kein Palindrom

Ausgabe 2:

Geben Sie die Zeichenfolge zur Überprüfung ein:

Cocoococ

Cocoococ ist ein Palindrom

Einige abschließende Gedanken zur Palindromfunktion in Java

Zusammenfassend lässt sich sagen, dass Ihre Aufgabe bei Palindromen darin besteht, Folgendes zu tun: Charaktere vergleichen am linken und rechten Ende einer Zeichenfolge. Wenn sie nicht übereinstimmen, ist die Zeichenfolge selbst kein Palindrom. Der nächste Schritt besteht darin, die beiden Zeichen zu vergleichen, die am linken und rechten Ende einer Zeichenfolge an zweiter Stelle stehen, und dann in Richtung der Mitte der Zeichenfolge fortzufahren oder bis Sie ein Paar finden, das nicht übereinstimmt.

Wenn Sie die Mitte der Zeichenfolge erreichen, haben Sie tatsächlich ein Palindrom – oder zumindest ein Teil dieser Zeichenfolge kann als Palindrom betrachtet werden. Wenn die Zeichenfolge „madam“ lautet, ist die gesamte Zeichenfolge ein Palindrom. Wenn die Zeichenfolge „amadam“ ist, handelt es sich nicht um ein Palindrom, aber das „ada“ zur Mitte hin kann als Palindrom betrachtet werden.