Die längste Teilzeichenfolge, in der benachbarte Zeichen keine angrenzenden englischen Buchstaben haben

Im Bereich der String-Manipulation sind das Identifizieren von Mustern und das Extrahieren aussagekräftiger Teilstrings häufige Aufgaben. Ein interessantes Problem besteht darin, die längste Teilzeichenfolge zu finden, in der keine benachbarten Zeichen benachbarte englische Buchstaben sind. In diesem Artikel befassen wir uns mit einer effizienten Lösung dieses Problems mithilfe von C++ und stellen klare Erklärungen und Beispieltestfälle bereit.

Problemstellung

Angesichts einer Zeichenfolge aus englischen Kleinbuchstaben müssen wir die Länge der längsten Teilzeichenfolge ermitteln, in der keine benachbarten Zeichen benachbarte englische Buchstaben sind. Beispielsweise ist in der Zeichenfolge „abacabx“ die längste Teilzeichenfolge, die diese Bedingung erfüllt, „abx“ mit einer Länge von 3.

Methoden und Algorithmen

Um dieses Problem zu lösen, können wir die Greedy-Methode verwenden. Wir durchlaufen die angegebene Zeichenfolge und prüfen, ob das aktuelle Zeichen und das vorherige Zeichen benachbarte englische Buchstaben sind. Wenn ja, beginnen wir einen neuen Teilstring. Andernfalls erweitern wir den vorhandenen Teilstring. Indem wir den längsten Teilstring jedes Mal aktualisieren, wenn seine Länge das vorherige Maximum überschreitet, können wir das gewünschte Ergebnis finden.

C++-Implementierung

Dies ist der C++-Code, der das Problem &minus löst,

#include <iostream>
#include <string>
using namespace std;

int findLongestSubstring(const string& str) {
   int maxLength = 0;
   int currentLength = 1;
   
   for (int i = 1; i < str.length(); i++) {
      if (abs(str[i] - str[i - 1]) != 1) {
         currentLength++;
      } else {
         maxLength = max(maxLength, currentLength);
         currentLength = 1;
      }
   }
   
   maxLength = max(maxLength, currentLength);
    return maxLength;
}

int main() {
   string inputString = "abacabx";
   int longestSubstringLength = findLongestSubstring(inputString);
   
   cout << "Longest substring length: " << longestSubstringLength << endl;
   
   return 0;
}

Ausgabe

Longest substring length: 3

Code-Erklärung

Die Funktion findLongestSubstring akzeptiert eine Eingabezeichenfolge als Parameter und gibt die Länge der längsten Teilzeichenfolge nicht benachbarter englischer alphabetischer Zeichen zurück.

Wir initialisieren maxLength und currentLength auf 0 bzw. 1. Dann durchlaufen wir die Zeichenfolge ab dem zweiten Zeichen. Wenn die absolute Differenz zwischen dem aktuellen Zeichen und dem vorherigen Zeichen nicht gleich 1 ist, wird currentLength erhöht, um die aktuelle Teilzeichenfolge zu erweitern. Andernfalls, wenn die aktuelle Länge das vorherige Maximum überschreitet, aktualisieren wir maxLength und setzen currentLength auf 1 zurück.

Abschließend geben wir die gefundene maximale Länge zurück. In der Hauptfunktion stellen wir eine Beispieleingabezeichenfolge „abacabx“ bereit und geben die Länge der längsten Teilzeichenfolge aus.

Beispieltestfälle

Betrachten wir die Beispielzeichenfolge „abacabx“, um unsere Lösung zu demonstrieren.

Eintreten

string inputString = "abacabx";

In diesem Beispiel ist die längste Teilzeichenfolge ohne angrenzende englische alphabetische Zeichen „abx“ mit einer Länge von 3.

Fazit

Durch die Anwendung einer einfachen und effizienten Methode haben wir das Problem, mit C++ die längste nicht benachbarte englische Buchstabenteilzeichenfolge zu finden, erfolgreich gelöst. Wenn Sie den Code und die bereitgestellten Erklärungen verstehen, können Sie ähnliche Probleme im Zusammenhang mit der Zeichenfolgenmanipulation lösen.

Das obige ist der detaillierte Inhalt vonDie längste Teilzeichenfolge, in der benachbarte Zeichen keine angrenzenden englischen Buchstaben haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!