C++-Programm, um herauszufinden, ob eine bestimmte Zeichenfolge eine sich wiederholende Teilsequenz mit einer Länge von 2 oder mehr hat

Suchen Sie bei einer gegebenen Zeichenfolge eine Teilfolge mit einer Länge von mindestens zwei, die in der Zeichenfolge wiederholt wird. Die Indizes der Teilsequenzelementnummern können nicht in derselben Reihenfolge sein.

string s = "PNDPNSP";
print("Repeated subsequence of length 2 or more: ", (check(s) ? "Yes" : "No"));

Sehen wir uns unten ein paar Beispiele an, um zu verstehen, wie dieser Ansatz in verschiedenen Situationen funktioniert -

Beispiel 1 - str = "PNDPNSP"

Erläuterung − Hier ist die Antwort wahr, da die Zeichenfolge eine wiederkehrende Teilsequenz „PN“ enthält.

Beispiel 2 - str = "PPND"

Erklärung – Hier ist die Antwort falsch, da es in der Zeichenfolge keine wiederholte Teilfolge mit einer Länge von mindestens zwei gibt.

Beispiel 3 − str = "PPNP"

Erklärung - Hier ist die Antwort richtig, da die „PP“-Indizes 0 und 1 sowie die „PP“-Indizes 1 und 3 existieren und die verwendeten „PP“ in der Teilsequenz nacheinander unterschiedliche Indizes haben. (0-basierter Index)

Die chinesische Übersetzung von

Brute-Force-Ansatz

lautet:

Brute-Force-Ansatz

Diese Methode generiert alle möglichen Teilsequenzen der Länge 2 (Mindestlänge) und stellt fest, ob wir diese Teilsequenz bereits mit der gefundenen Teilsequenz gesehen haben. Wenn die Teilsequenz bereits existiert, geben wir „true“ zurück und beenden das Programm; andernfalls geben wir nach Abschluss der Iteration „false“ zurück, wenn wir nichts gefunden haben.

Im schlimmsten Fall existiert diese Teilsequenz möglicherweise nicht und wir generieren am Ende alle möglichen Ergebnisse.

Teilfolgen zweier Längen berechnen und speichern. Angenommen, Sie hashen die berechnete Teilsequenz, um die Einfügung und Suche von O(1) zu erreichen, dann wird daraus O(n^2). Die gesamte Teilfolge ist ebenfalls O(n^2), also ist es auch der Speicherplatz.

Modifizierte längste gemeinsame Teilsequenz (LCS)

LCS-Algorithmus findet die längste gemeinsame Teilsequenz in 2 Strings. Es handelt sich um eine standardmäßige dynamische Programmiermethode, die eine iterative Methode zweidimensionaler Matrizen verwendet. Die Zeitkomplexität beträgt O(n^2). Wir werden in der geänderten Methode nur nach der angegebenen Zeichenfolge selbst suchen. Dennoch prüfen wir auch, ob der Index der aktuellen Position nicht derselbe ist.

Beispiel

Schauen Sie sich den folgenden C++-Code an, um den modifizierten Algorithmus für die längste gemeinsame Teilsequenz zu implementieren, der unserer Methode dabei hilft, sich wiederholende Teilsequenzen mit einer Länge von 2 oder mehr zu finden -

#include <iostream>
using namespace std;
bool modifiedLongestCommonSubsequence(string s) {
   int n = s.length();
   int dp[n+1][n+1];
   for (int i=0; i<=n; i++)
      fill(dp[i], dp[i]+n+1, 0);
   for (int i=1; i<=n; i++) {
      for (int j=1; j<=n; j++) {
         if (s[i-1]==s[j-1] && i!=j) {
            dp[i][j] = 1 + dp[i-1][j-1];
         }
         else {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
         }
      }
   }
   if(dp[n][n] > 1) return true;
   return false;
}
int main() {
   string str = "PNDPNSP";
   cout << "Repeated subsequence of length 2 or more: " << (modifiedLongestCommonSubsequence(str) ? "Yes" : "No");
   return 0;
}

Ausgabe

Repeated subsequence of length 2 or more: Yes

Natürlich ist die zeitliche und räumliche Komplexität O(n^2), aber wenn man sich die erste Methode ansieht, ist sie eleganter und erzeugt leicht einen Hash von O(1).

Verbesserte Lösung

In dieser Methode werden wir versuchen, einige Beobachtungen basierend auf der vorherigen Methode zu machen.

Beobachtung 1 − Wenn ein Zeichen mehr als zweimal vorkommt, ist die Antwort immer wahr. Mal sehen, warum?

Beispiel – In der Zeichenfolge str = „AVHJFBABVNHFA“ haben wir „AAA“ an den Positionen 0, 6 und 12. Also Wir können „AA“ bei Index 0 und 6 als Teilsequenz und „AA“ bei Index 6 und 12 als Teilsequenz haben als ein anderer.

Beobachtung 2 – Wenn ein Zeichen nur einmal wiederholt wird, kann es nicht zu unseren Ergebnissen beitragen Teilsequenz, da es nur in höchstens einer Teilsequenz verfügbar sein wird. es wird nicht funktionieren Weil wir mindestens zwei Teilfolgen brauchen. Wir können also alle Zeichen entfernen oder ignorieren geschah gleichzeitig.

Beobachtung 3 − Wenn eine Zeichenfolge ein Palindrom ist und die ersten beiden Beobachtungen zutreffen, dann lautet die Antwort Immer falsch, es sei denn, die Zeichenfolgenlänge ist ungerade. Mal sehen, warum?

Beispiel – String str = „PNDDNP“

Erklärung – Nun, die Zeichen sind nicht in der richtigen Reihenfolge, sodass wir sie nie finden können Die Teilsequenzen haben die gleiche Reihenfolge, daher ist dies nicht möglich.

Beispiel

Basierend auf allen drei oben genannten Beobachtungen kommen wir zu dem Schluss, dass unsere Antwort richtig ist, wenn wir alle Zeichen entfernen, die einmal in der Zeichenfolge vorkommen, und dann prüfen, ob ein bestimmtes Zeichen mehr als zweimal vorkommt oder ob die Zeichenfolge kein Palindrom ist. Sehen wir uns die verbesserte Lösung an, die in C++ implementiert wurde -

#include <iostream>
using namespace std;
bool isPalindrome(string s) {
   for(int i=0;i<s.size()/2;i++) {
      if(s[i]!=s[s.size()-1-i]) {
         return false;
      }
   }
   return true;
}
bool check(string s) {
   int hash[26] = {0};
   for (int i = 0; i < s.size(); i++) {
      hash[s[i]-'a']++;
      if (hash[s[i]-'a'] > 2) {
         return true;
      }
   }
   int k = 0;
   string mstr = "";
   for (int i = 0; i < s.size(); i++) {
      if (hash[s[i]-'a'] > 1) {
         mstr[k++] = s[i];
      }
   }
   if (isPalindrome(mstr)) {
      return false;
   }
   return true;
}
int main() {
   string s = "PNDPNSP";
   cout << "Repeated subsequence of length 2 or more: " << (check(s) ? "Yes" : "No");
   return 0;
}

Ausgabe

Repeated subsequence of length 2 or more: Yes

Fazit

Wir kamen zu dem Schluss, dass die Verwendung von Beobachtungen und Hashes der beste Weg ist, dieses Problem zu lösen. Die Zeitkomplexität beträgt O(n). Die Raumkomplexität liegt ebenfalls in der Größenordnung von O(n), wodurch eine neue Zeichenfolge und ein konstanter 26-Zeichen-Hash erstellt werden.

Das obige ist der detaillierte Inhalt vonC++-Programm, um herauszufinden, ob eine bestimmte Zeichenfolge eine sich wiederholende Teilsequenz mit einer Länge von 2 oder mehr hat. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!