Palindromische Teilstring-Abfrage in C++
In diesem Tutorial müssen wir die palindromische Teilzeichenfolgenabfrage einer bestimmten Zeichenfolge lösen. Das Lösen von Palindrom-Teilzeichenfolgenabfragen ist viel komplexer als das Lösen regulärer Abfragen in C++. Es erfordert komplexeren Code und komplexere Logik.
In diesem Tutorial haben wir String-Str- und Q-Substring-Abfragen [L...R] bereitgestellt, von denen jede zwei Werte L und R hat. Unser Ziel ist es, ein Programm zu schreiben, das eine Abfrage löst, um festzustellen, ob Teilzeichenfolge[L...R] ein Palindrom ist. Wir müssen bestimmen, ob der im Bereich L bis R gebildete Teilstring ein Palindrom ist, um jede Abfrage zu lösen. Zum Beispiel -
Let's input "abbbabaaaba" as our input string. The queries were [3, 13], [3, 11], [5, 8], [8, 12] It is necessary to determine whether the substring is a plaindrome A palindrome is "abaaabaaaba" (3, 13) . It is not possible to write "baaa" as a palindrome [3, 11]. As in [5, 8]: "aaab" cannot be a palindrome. There is a palindrome in "baaab" ([3, 12]).
Lösungsmethode
Naive Methode
Hier müssen wir das Palindrom finden, indem wir prüfen, ob die Teilzeichenfolge zwischen dem Indexbereich L bis R liegt. Daher müssen wir eine Abfrage für alle Teilzeichenfolgen durchführen um zu sehen, ob es ein Palindrom ist. Da es Q-Anfragen gibt, dauert die Beantwortung jeder Anfrage 0(N). Im schlimmsten Fall dauert es 0(Q.N) Zeit.
Beispiel
#include <bits/stdc++.h> using namespace std; int isPallindrome(string str){ int i, length; int flag = 0; length = str.length(); for(i=0;i < length ;i++){ if(str[i] != str[length-i-1]) { flag = 1; break; } } if (flag==1) return 1; return 0; } void solveAllQueries(string str, int Q, int query[][2]){ for(int i = 0; i < Q; i++){ isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))? cout<<"Palindrome\n":cout<<"Not palindrome!\n"; } } int main() { string str = "abccbeba"; int Q = 3; int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}}; solveAllQueries(str, Q, query); return 0; }
Ausgabe
Palindrome Palindrome Not palindrome!
Dynamische Programmiermethode
Die Verwendung einer dynamischen Programmiermethode zur Lösung des Problems ist eine effektive Option. Um dieses Problem zu lösen, müssen wir ein DP-Array erstellen, bei dem es sich um ein zweidimensionales Array handelt, das einen booleschen Wert enthält, der angibt, ob substring[i...j] ein Palindrom von DP[i][j] ist. p>
erstellt diese DP-Matrix und überprüft alle L-R-Werte für jede Abfrage.
Beispiel
#include <bits/stdc++.h> using namespace std; void computeDP(int DP[][50], string str){ int length = str.size(); int i, j; for (i = 0; i < length; i++) { for (j = 0; j < length; j++) DP[i][j] = 0; } for (j = 1; j <= length; j++) { for (i = 0; i <= length - j; i++) { if (j <= 2) { if (str[i] == str[i + j - 1]) DP[i][i + j - 1] = 1; } else if (str[i] == str[i + j - 1]) DP[i][i + j - 1] = DP[i + 1][i + j - 2]; } } } void solveAllQueries(string str, int Q, int query[][2]){ int DP[50][50]; computeDP(DP, str); for(int i = 0; i < Q; i++){ DP[query[i][0] - 1][query[i][1] - 1]?cout <<"not palindrome!\n":cout<<"palindrome!\n"; } } int main() { string str = "abccbeba"; int Q = 3; int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}}; solveAllQueries(str, Q, query); return 0; }
Ausgabe
palindrome! not palindrome! palindrome!
Fazit
In diesem Tutorial haben wir gelernt, wie man eine palindromische Teilzeichenfolgenabfrage mit C++-Code löst. Wir können diesen Code auch in Java, Python und anderen Sprachen schreiben. Dieser Code ist einer der komplexesten und langwierigsten. Palindrom-Abfragen sind schwieriger als normale Teilstring-Abfragen und erfordern eine sehr präzise Logik. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.
Das obige ist der detaillierte Inhalt vonPalindromische Teilstring-Abfrage in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen



Laden Sie die neueste Version der Ticketbuchungs-App 12306 herunter, mit der jeder sehr zufrieden ist. Es gibt viele Ticketquellen, die in der Software bereitgestellt werden -Namenauthentifizierung zum Online-Kauf von Tickets. Alle Benutzer können ganz einfach Reisetickets und Flugtickets kaufen und verschiedene Ermäßigungen genießen. Sie können auch im Voraus mit der Buchung beginnen, um Tickets zu erhalten. Damit können Sie mit einem Klick dorthin fahren, wo Sie möchten, und so das Reisen einfacher und bequemer gestalten Noch komfortabler: Der Herausgeber stellt die Details jetzt online dar. Bietet 12306 Benutzern die Möglichkeit, historische Ticketkaufaufzeichnungen einzusehen. 1. Öffnen Sie Railway 12306, klicken Sie unten rechts auf „Mein“ und dann auf „Meine Bestellung“. 2. Klicken Sie auf der Bestellseite auf „Bezahlt“. 3. Auf der kostenpflichtigen Seite

Wie kann ich meine akademischen Qualifikationen auf Xuexin.com überprüfen? Sie können Ihre akademischen Qualifikationen auf Xuexin.com überprüfen. Viele Benutzer wissen nicht, wie sie ihre akademischen Qualifikationen auf Xuexin.com überprüfen können Benutzer kommen vorbei und schauen sich um! Tutorial zur Nutzung von Xuexin.com: So überprüfen Sie Ihre akademischen Qualifikationen auf Xuexin.com 1. Zugang zu Xuexin.com: https://www.chsi.com.cn/ 2. Website-Abfrage: Schritt 1: Klicken Sie auf die Adresse von Xuexin.com Um die Startseite aufzurufen, klicken Sie oben auf [Bildungsabfrage]; Schritt 2: Klicken Sie auf der neuesten Webseite auf [Abfrage], wie durch den Pfeil in der Abbildung unten dargestellt. Schritt 3: Klicken Sie dann auf der neuen Seite auf [Anmelden bei akademischer Kreditdatei]. Schritt 4: Geben Sie auf der Anmeldeseite die Informationen ein und klicken Sie auf [Anmelden].

MySQL und PL/SQL sind zwei unterschiedliche Datenbankverwaltungssysteme, die die Merkmale relationaler Datenbanken bzw. prozeduraler Sprachen darstellen. In diesem Artikel werden die Ähnlichkeiten und Unterschiede zwischen MySQL und PL/SQL anhand konkreter Codebeispiele zur Veranschaulichung verglichen. MySQL ist ein beliebtes relationales Datenbankverwaltungssystem, das Structured Query Language (SQL) zum Verwalten und Betreiben von Datenbanken verwendet. PL/SQL ist eine für Oracle-Datenbanken einzigartige prozedurale Sprache und wird zum Schreiben von Datenbankobjekten wie gespeicherten Prozeduren, Triggern und Funktionen verwendet. Dasselbe

Wenn Sie das Aktivierungsdatum mit einem Apple-Mobiltelefon überprüfen möchten, überprüfen Sie es am besten anhand der Seriennummer im Mobiltelefon. Sie können es auch überprüfen, indem Sie die offizielle Website von Apple besuchen, es an einen Computer anschließen und einen Drittanbieter herunterladen Software eines Drittanbieters, um dies zu überprüfen. Wie kann ich das Aktivierungsdatum eines Apple-Mobiltelefons überprüfen? Antwort: Abfrage der Seriennummer, Abfrage der offiziellen Apple-Website, Abfrage der Software eines Drittanbieters 1. Der beste Weg für Benutzer ist, die Seriennummer ihres Mobiltelefons zu kennen Sie können die Seriennummer sehen, indem Sie „Einstellungen“, „Allgemein“, „Über dieses Gerät“ öffnen. 2. Anhand der Seriennummer können Sie nicht nur das Aktivierungsdatum Ihres Mobiltelefons ermitteln, sondern auch die Mobiltelefonversion, die Herkunft des Mobiltelefons, das Fabrikdatum des Mobiltelefons usw. überprüfen. 3. Benutzer besuchen die offizielle Website von Apple, um technischen Support zu finden, finden die Spalte „Service und Reparatur“ unten auf der Seite und überprüfen dort die iPhone-Aktivierungsinformationen. 4. Benutzer

Titel: Wie kann ich mit Oracle abfragen, ob eine Tabelle gesperrt ist? In der Oracle-Datenbank bedeutet Tabellensperre, dass, wenn eine Transaktion einen Schreibvorgang für die Tabelle ausführt, andere Transaktionen blockiert werden, wenn sie Schreibvorgänge für die Tabelle ausführen oder strukturelle Änderungen an der Tabelle vornehmen möchten (z. B. Spalten hinzufügen, Zeilen löschen). , usw.). Im eigentlichen Entwicklungsprozess müssen wir häufig abfragen, ob die Tabelle gesperrt ist, um damit verbundene Probleme besser beheben und beheben zu können. In diesem Artikel wird erläutert, wie Sie mithilfe von Oracle-Anweisungen abfragen, ob eine Tabelle gesperrt ist, und es werden spezifische Codebeispiele aufgeführt. Um zu überprüfen, ob der Tisch gesperrt ist, haben wir

Das Forum ist eine der häufigsten Website-Formen im Internet. Es bietet Benutzern eine Plattform zum Teilen von Informationen, zum Austauschen und zur Diskussion. Discuz ist ein häufig verwendetes Forenprogramm und ich glaube, dass viele Webmaster bereits sehr vertraut damit sind. Während der Entwicklung und Verwaltung des Discuz-Forums ist es häufig erforderlich, die Daten in der Datenbank zur Analyse oder Verarbeitung abzufragen. In diesem Artikel geben wir einige Tipps zum Abfragen des Speicherorts der Discuz-Datenbank und stellen spezifische Codebeispiele bereit. Zunächst müssen wir die Datenbankstruktur von Discuz verstehen

In diesem Artikel wird ausführlich erläutert, wie PHP die Zeichenfolge von der Startposition zur Endposition einer Zeichenfolge in einer anderen Zeichenfolge zurückgibt. Der Herausgeber hält dies für recht praktisch, daher teile ich es Ihnen als Referenz mit diesem Artikel können Sie etwas abgewinnen. Verwenden Sie die Funktion substr() in PHP, um Teilzeichenfolgen aus einer Zeichenfolge zu extrahieren. Die Funktion substr() kann Zeichen innerhalb eines angegebenen Bereichs aus einer Zeichenfolge extrahieren. Die Syntax lautet wie folgt: substr(string,start,length) wobei: string: der ursprüngliche String, aus dem der Teilstring extrahiert werden soll. start: Der Index der Startposition des Teilstrings (beginnend bei 0). Länge (optional): Die Länge des Teilstrings. Wenn nicht angegeben, dann

Wie kann ich den aktuellen Preis von Tongshen Coin überprüfen? Token ist eine digitale Währung, die zum Kauf von Gegenständen, Diensten und Vermögenswerten im Spiel verwendet werden kann. Es ist dezentralisiert, das heißt, es wird nicht von Regierungen oder Finanzinstituten kontrolliert. Transaktionen von Tongshen Coin werden auf der Blockchain durchgeführt, einem verteilten Hauptbuch, das die Informationen aller Tongshen Coin-Transaktionen aufzeichnet. Um den aktuellen Token-Preis zu überprüfen, können Sie die folgenden Schritte ausführen: Wählen Sie eine zuverlässige Website oder App zur Preisprüfung. Zu den häufig verwendeten Websites zur Preisabfrage gehören: CoinMarketCap: https://coinmarketcap.com/Coindesk: https://www.coindesk.com/ Binance: https://www.bin
