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;
}

Ausgabe

Length of longest substring to be deleted: 1

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;
}

Ausgabe

Length of longest substring to be deleted: 1

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!