Finden Sie mithilfe der dynamischen Programmierung verschiedene palindromische Teilzeichenfolgen in einer bestimmten Zeichenfolge

Einführung

In diesem Tutorial haben wir eine Methode besprochen, um alle möglichen palindromischen Teilzeichenfolgen mithilfe einer Eingabezeichenfolge zu finden. Um diese Aufgabenmethode zu implementieren, verwenden wir die Programmiersprache C++ und ihre Funktionen.

Ein Palindrom ist eine Zeichenfolge, die von vorne nach hinten und von hinten nach vorne gleich lautet. Zum Beispiel ist „Mom“ eine Palindrom-Zeichenfolge. In diesem Tutorial nehmen wir einen String und finden darin alle möglichen palindromischen Teilstrings.

Die chinesische Übersetzung von

Beispiel 1

lautet:

Beispiel 1

String = abcaa

Ausgabe

The possible palindromic substrings are : a, b, c, aa, aaa, aba, and aca.

Im obigen Beispiel kann die Eingabezeichenfolge 7 Palindrom-Teilzeichenfolgen generieren: „a“, „b“, „c“, „aa“, „aaa“, „aba“ und „aca“.

Die chinesische Übersetzung von

Beispiel 2

lautet:

Beispiel 2

String = “abcd”

Ausgabe

a, b, c, and d.

Im obigen Beispiel können mit der Eingabezeichenfolge nur 4 Palindrom-Teilzeichenfolgen der Länge 1 erhalten werden. Da die Eingabezeichenfolge keine wiederholten Zeichen enthält, hat keine Teilzeichenfolge eine Länge größer als 1.

Funktion, die als Beispiel für die Implementierung verwendet wird

• size() − Dies ist eine stringähnliche Funktion, die die Anzahl der Zeichen in der angegebenen Zeichenfolge zurückgibt. Es werden keine Parameter akzeptiert.

Grammatik

string_name.size();

Beispiel

str.size();

• begin() − Diese Bibliotheksfunktion ist in STL definiert. Es gibt den Startiterationswert des Kartencontainers an.

Syntax: Kartenname.begin(); Beispiel: mp.begin();

• end() − Diese Bibliotheksfunktion ist in STL definiert. Es gibt den Enditerationswert des Kartencontainers an.

Grammatik

map_name.end();

Beispiel

mp.end();

• substr() − Es generiert einen Teilstring unter Verwendung des Eingabestrings. Es ist in der Header-Datei string.h definiert. Es akzeptiert zwei Parameter (pos, len). Pos ist der Startwert der Teilzeichenfolge und len ist die Anzahl der Zeichen in der Teilzeichenfolge.

Grammatik

string_name.substr(pos, len);

Beispiel

str.substr();

Algorithmus

• Betrachten Sie eine bestimmte Zeichenfolge und finden Sie alle darin enthaltenen Palindrom-Teilzeichenfolgen.

• Finden Sie alle palindromischen Teilzeichenfolgen der Eingabezeichenfolge, indem Sie über die Zeichenfolge iterieren.

• Erstellen Sie zwei Arrays für Palindrom-Teilzeichenfolgen ungerader und gerader Länge.

• Speichern Sie die Werte zweier Arrays in einer Hash-Map.

• Drucken Sie alle in Hashmap gespeicherten Werte.

• Die Anzahl der Teilzeichenfolgen entspricht der Länge der Hash-Map. Durchlaufen Sie die Hash-Map und drucken Sie jeden Wert aus. Verwenden Sie eine for-Schleife, um auf jedes Element in der Karte zuzugreifen und den zugehörigen Wert auszugeben. Schließlich sollte die Anzahl der gedruckten Werte mit der Größe der Hash-Map übereinstimmen.

Logik 1 Beispiel

In diesem Abschnitt implementieren wir eines der oben genannten Beispiele mithilfe der Konzepte der Programmiersprache C++. Wir betrachten eine Eingabezeichenfolge in der Funktion main() und verwenden sie, um eine Ausgabe zu generieren.

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

//user defined program to find the palindrome substrings
void palindromeSubStrings(string str){
   map<string, int> mp;
   int l = str.size();
   
   //store odd and even length palindrome substrings
   int R[2][l+1];
   
   //Using guards for effortless iteration over the input string and generating all palindrome
   // substrings
   str = "@" + str + "#";
   
   for (int i = 0; i <= 1; i++) {
      int r = 0;  
      R[i][0] = 0;

      int x = 1;
      while (x <= l){
            
         while (str[x - r - 1] == str[x + i + r])
            r++; 
           
         R[i][x] = r;
         int a = 1;
         while ((R[i][x - a] != r - a) && (a < r)){
            R[i][x + a] = min(R[i][x - a],r - a);
            a++;
         }
         r = max(r - a,0);
         x += a;
      }
   }
   //storing the substring without guards
   str = str.substr(1, l);
      
   mp[string(1, str[0])]=1;
   for (int x = 1; x <= l; x++){
      for (int y = 0; y <= 1; y++)
            for (int r = R[y][x]; r > 0; r--)
               mp[str.substr(x - r - 1, 2 * r + y)]=1;
         mp[string(1, str[x])]=1;
   }
      
   //print the palindrome substrings stored in the Hashmap
   cout << "Palindrome substrings are as listed: ";
   map<string, int>::iterator xx;
   for (xx = mp.begin(); xx!=mp.end(); ++xx)
      cout << (*xx).first << endl;
}
   
//Controlling code
int main(){
   //calling the user-defined function and passing a string as argument
   palindromeSubStrings("abcaa");
   return 0;
}

Ausgabe

Palindrome substrings are listed as:
a
aa
b
c

Logic 2-Beispiel

Wir implementieren ein weiteres Beispiel mithilfe der dynamischen Programmiermethode. Bei der dynamischen Programmierung werden Aufgaben in Teilaufgaben zerlegt und einzeln gelöst, um Zeit und Komplexität zu reduzieren.

#include <iostream>
#include <vector>
using namespace std;
//User defined function to find the palindromic substring 
int find(string str){
   int a = str.size();
   //defined dpg array
      vector<vector<bool> > dpg(a, vector<bool>(a, false));
      for (int x = 0; x < a; x++) {

         dpg[x][x] = 1;
  
         if (x < a && str[x] == str[x + 1]) {
            dpg[x][x + 1] = 1;
         }
      }
   // Finding length of different substrings
   for (int l = 3; l <= a; l++) {
      for (int x = 0; x + l - 1 < a; x++){
         if (str[x] == str[x + (l - 1)]
         && dpg[x + 1][x + (l - 1) - 1]) {
            dpg[x][x + (l - 1)] = true;
         }
      }
   }
 
 
   vector<int> kmp(a, 0);
   for (int x = 0; x < a; x++) {
     
      int y = 0, m = 1;
      while (m + x < a) {
         if (str[y + x] == str[m + x]){
            dpg[m + x - y][m + x] = false;
            kmp[m++] = ++y;
         }
         else if (y > 0) {
            y = kmp[y - 1];
         }
         else {
            kmp[m++] = 0;
         }
      }
   }

   int cnt = 0;
   for (int x = 0; x < a; x++) {
      string str1;
      for (int y = x; y < a; y++) {
         str1 += str[y];
         if (dpg[x][y]) {
            //counting number of palindromic substrings formed using the string
               cnt++;
               cout << str1 << '\n';
         }
      }
   }
   cout << "Total number of palindromes are "
   << cnt << '\n';
   return 0;
}
 
//Controller
int main(){
   string str = "abaa";
   find(str);
   return 0;
}

Ausgabe

a
aba
b
aa
Total number of palindromes are 4

Fazit

In diesem Tutorial haben wir zwei Methoden entwickelt, um alle möglichen Palindrom-Teilzeichenfolgen in einer bestimmten Zeichenfolge zu finden. Wir verstehen die Aufgabe anhand von zwei Beispielen und schreiben einen Beispielcode in der Programmiersprache C++. Wir verwenden Hash-Maps und Vektoren, um palindromische Teilzeichenfolgen zu speichern und das Beispiel zu implementieren. Die Verwendung einer Hash-Map hilft beim Abgleichen von Schlüssel-Wert-Paaren und wir können je nach Anforderung viele Hash-Funktionen verwenden. Wir haben auch einige Bibliotheksfunktionen verwendet, um die Beispiele zu implementieren.

Das obige ist der detaillierte Inhalt vonFinden Sie mithilfe der dynamischen Programmierung verschiedene palindromische Teilzeichenfolgen in einer bestimmten Zeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!