Heim > Backend-Entwicklung > C++ > Die Länge des längsten Teilstrings, der entfernt werden muss, damit ein String einem anderen String entspricht

Die Länge des längsten Teilstrings, der entfernt werden muss, damit ein String einem anderen String entspricht

WBOY
Freigeben: 2023-09-16 17:53:06
nach vorne
806 Leute haben es durchsucht

Die Länge des längsten Teilstrings, der entfernt werden muss, damit ein String einem anderen String entspricht

In diesem Artikel besprechen wir das Problem, die Länge des längsten Teilstrings zu ermitteln, der entfernt werden muss, um einen String einem anderen gleich zu machen. Wir werden zunächst die Problemstellung verstehen und dann einfache und effiziente Wege zur Lösung des Problems sowie deren jeweilige algorithmische und zeitliche Komplexität untersuchen. Abschließend werden wir die Lösung in C++ implementieren.

Problemstellung

Bestimmen Sie anhand zweier Strings A und B die Länge des längsten Teilstrings, der aus String A entfernt werden muss, damit er gleich String B ist.

Naive Methode

Der einfachste Weg besteht darin, alle möglichen Teilzeichenfolgen von Zeichenfolge A zu generieren, sie einzeln zu entfernen und dann zu prüfen, ob die resultierende Zeichenfolge mit Zeichenfolge B übereinstimmt. Wenn ja, speichern wir die Länge des entfernten Teilstrings. Zum Schluss geben wir die maximale Länge aller entfernten Teilzeichenfolgen zurück.

Algorithmus (naiv)

  • MaxLength auf 0 initialisieren.

  • Generieren Sie alle möglichen Teilzeichenfolgen von Zeichenfolge A

  • Entfernen Sie jeden Teilstring aus String A und prüfen Sie, ob der resultierende String mit String B übereinstimmt.

  • Wenn ja, aktualisieren Sie maxLength auf den Maximalwert von maxLength und löschen Sie die Teilzeichenfolgenlänge.

  • Gibt die maximale Länge zurück.

C++-Code (einfach)

Beispiel

#include <iostream>
#include <string>
#include <algorithm>

int longestSubstringToDelete(std::string A, std::string B) {
   int maxLength = 0;
   
   for (int i = 0; i < A.length(); i++) {
      for (int j = i; j < A.length(); j++) {
         std::string temp = A;
         temp.erase(i, j - i + 1);
   
         if (temp == B) {
            maxLength = std::max(maxLength, j - i + 1);
         }
      }
   }
   
   return maxLength;
}

int main() {
   std::string A = "abcde";
   std::string B = "acde";
   
   std::cout << "Length of longest substring to be deleted: " << longestSubstringToDelete(A, B) << std::endl;
   
   return 0;
}
Nach dem Login kopieren

Ausgabe

Length of longest substring to be deleted: 1
Nach dem Login kopieren
Nach dem Login kopieren

Zeitkomplexität (naiv) – O(n^3), wobei n die Länge von String A ist.

Effiziente Methode

Eine effiziente Möglichkeit, dieses Problem zu lösen, besteht darin, die längste gemeinsame Teilfolge (LCS) zweier Zeichenfolgen zu finden. Die Länge des längsten Teilstrings, der in String A gelöscht werden muss, damit er gleich String B ist, ist die Differenz zwischen der Länge von String A und der Länge von LCS.

Algorithmus (effizient)

  • Finden Sie die längste gemeinsame Teilfolge (LCS) von String A und String B.

  • Gibt die Differenz zwischen der Länge von Zeichenfolge A und der Länge von LCS zurück.

C++-Code (effizient)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int longestCommonSubsequence(std::string A, std::string B) {
   int m = A.length();
   int n = B.length();
   std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
   
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (A[i - 1] == B[j - 1]) {
            
            dp[i][j] = 1 + dp[i - 1][j - 1];
         } else {
            dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
         }
      }
   }
   return dp[m][n];
}

int longestSubstringToDelete(std::string A, std::string B) {
   int lcsLength = longestCommonSubsequence(A, B);
   return A.length() - lcsLength;
}

int main() {
   std::string A = "abcde";
   std::string B = "acde";
   std::cout << "Length of longest substring to be deleted: " << longestSubstringToDelete(A, B) << std::endl;
   
   return 0;
}
Nach dem Login kopieren

Ausgabe

Length of longest substring to be deleted: 1
Nach dem Login kopieren
Nach dem Login kopieren

Zeitkomplexität (effizient) – O(m * n), wobei m die Länge von String A und n die Länge von String B ist.

Fazit

In diesem Artikel untersuchen wir das Problem, die Länge des längsten Teilstrings zu ermitteln, der entfernt werden muss, um einen String einem anderen gleich zu machen. Wir diskutieren einfache, aber effiziente Methoden zur Lösung dieses Problems sowie deren algorithmische und zeitliche Komplexität. Effiziente Methoden nutzen das Konzept der längsten gemeinsamen Teilsequenz und erzielen im Vergleich zu naiven Methoden erhebliche Verbesserungen der Zeitkomplexität.

Das obige ist der detaillierte Inhalt vonDie Länge des längsten Teilstrings, der entfernt werden muss, damit ein String einem anderen String entspricht. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage