Berechnen Sie drei nicht überlappende Teilzeichenfolgen und verketten Sie sie zu einem Palindrom

Einführung

In diesem Tutorial erläutern wir eine Methode, um drei nicht überlappende Teilzeichenfolgen aus einem bestimmten String s zu finden. Wenn alle Teilzeichenfolgen miteinander kombiniert werden, bilden sie ein Palindrom. Zur Lösung dieser Aufgabe nutzen wir die String-Klassen-Funktionalität der Programmiersprache C++.

Ein Palindrom in einer Zeichenfolge bedeutet, dass die Zeichenfolge in Vorwärts- und Rückwärtsrichtung gleich lautet. Ein Beispiel für eine Palindrom-Zeichenfolge ist Madam.

Angenommen, es gibt eine Zeichenfolge „s“ und die Teilzeichenfolgen sind a, b, c. Wenn Sie a, b und c kombinieren, bilden sie eine Palindrom-Zeichenfolge. Dies ist ein Beispiel für das Verständnis der Logik des Problems.

Satzerklärung

String s = “abbacab”      
Acceptable substrings of length 3 are: “abb”, “bac”, and “bba”.

Wenn wir alle drei Teilzeichenfolgen verketten, ist die resultierende Zeichenfolge eine Palindromzeichenfolge, die abbbacbba lautet.

Grammatik

Die Funktion

size() gehört zur String-Klasse und wird verwendet, um die Größe des Eingabestrings und seine Zeichenlänge zu ermitteln.

string_name,size();  

Algorithmus

• Eingabezeichenfolge abrufen.

• Initialisieren Sie eine Zählervariable, die zum Verfolgen der Anzahl palindromischer Teilzeichenfolgen verwendet wird.

• Verwenden Sie 3 verschachtelte for-Schleifen, um 3 mögliche Teilzeichenfolgen definierter Länge zu generieren.

• Die erste innere Schleife wird von 0 auf die Stringlänge - 3 initialisiert.

• Die zweite innere Schleife wird auf die Zeichenfolgenlänge initialisiert – 2 von der ersten inneren Schleife + 1.

• Die äußere Schleife wird von der zweiten Schleife + 1 bis zur Zeichenfolgenlänge - 1 initialisiert.

• Nachdem Sie alle Teilzeichenfolgen gefunden haben, verketten Sie sie.

• Überprüfen Sie, ob das Teilstring-Palindrom vorhanden ist, und erhöhen Sie in diesem Fall den Wert der Zählervariable.

• Zählervariablenwert drucken.

Beispiel

Um den obigen Algorithmus mit C++ zu implementieren, nehmen wir eine Eingabezeichenfolge und generieren alle möglichen Kombinationen von Teilzeichenfolgen und berücksichtigen nur diese palindromischen Teilzeichenfolgen. Wenn ein solcher Teilstring möglich ist, wird die Zählervariable erhöht. Drucken Sie das Ergebnis der Zählervariablen aus.

#include <bits/stdc++.h>
using namespace std;
 
// user defined function to check formed substrings are palindrome or not
bool isStringPalin(int a, int b, int c, int d, int x, int y, string st){
   int begin = a, stop = y;
   while (begin < stop) {
      if (st[begin] != st[stop])
         return false;
 
      begin++;
      if (begin == b + 1)
         begin = c;
      stop--;
      if (stop == x - 1)
         stop = d;
   }
   return true;
}
 
// User defined function to count the number of useful substrings
int countSubString(string st){
   //Counting variable to count and return the number of substrings
   int ct = 0;
   int l = st.size();
 
   //It is to select the first substring
   for (int a = 0; a < l - 2; a++) {
      for (int b = a; b < l - 2; b++){
 
         // This loop selects the second useful substring
         for (int c = b + 1; c < l - 1; c++) {
            for (int d = c; d < l - 1; d++) {
 
               // this for loop will select the third substring
               for (int x = d + 1; x < l; x++) {
                  for (int y = x; y < l; y++) {
 
                     // If condition to check the selected substrings are forming palindrome or not
                     if (isStringPalin(a, b, c, d, x, y, st)) {
                        ct++;
                     }
                  }
               }
            }
         }
      }
   }
   // returning the count variable that stores the number of useful substrings
   return ct;
}
 
// Controlling code
int main(){
   string st = "abcab";
   cout << "The possible number of substrings are: "<< countSubString(st);
 
   return 0;
}

Ausgabe

The possible number of substrings are: 4

Fazit

Wir haben eine Methode entwickelt, um gültige Teilzeichenfolgen zu finden, die Palindrome bilden. Um diese Lösung zu implementieren, haben wir C++-Schleifen und if-Bedingungen verwendet. Um eines der Beispiele mit C++ zu implementieren, haben wir die Funktion size() und verschachtelte Schleifen verwendet. Verschachtelte Schleifen helfen dabei, Teilstrings unterschiedlicher Länge zu finden und die Funktion size() gibt die Größe des Strings zurück.

Das obige ist der detaillierte Inhalt vonBerechnen Sie drei nicht überlappende Teilzeichenfolgen und verketten Sie sie zu einem Palindrom. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!