La longueur de la sous-chaîne la plus longue qui doit être supprimée pour rendre une chaîne égale à une autre chaîne

Dans cet article, nous discuterons du problème de trouver la longueur de la sous-chaîne la plus longue qui doit être supprimée pour rendre une chaîne égale à une autre. Nous comprendrons d’abord l’énoncé du problème, puis explorerons des moyens simples et efficaces de résoudre le problème, ainsi que leurs complexités algorithmiques et temporelles respectives. Enfin, nous implémenterons la solution en C++.

Énoncé du problème

Étant donné deux chaînes A et B, déterminez la longueur de la sous-chaîne la plus longue qui doit être supprimée de la chaîne A afin qu'elle soit égale à la chaîne B.

Méthode naïve

Le moyen le plus simple consiste à générer toutes les sous-chaînes possibles de la chaîne A, à les supprimer une par une, puis à vérifier si la chaîne résultante est égale à la chaîne B. Si tel est le cas, nous stockons la longueur de la sous-chaîne supprimée. Enfin, nous renverrons la longueur maximale parmi toutes les sous-chaînes supprimées.

Algorithme (naïf)

• Initialisez maxLength à 0.

• Générer toutes les sous-chaînes possibles de la chaîne A

• Pour chaque sous-chaîne, supprimez-la de la chaîne A et vérifiez si la chaîne résultante est égale à la chaîne B.

• Si oui, mettez à jour maxLength avec la valeur maximale de maxLength et supprimez la longueur de la sous-chaîne.

• Renvoyer la longueur maximale.

Code C++ (simple)

Exemple

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

Sortie

Length of longest substring to be deleted: 1

Complexité temporelle (naïve) - O(n^3), où n est la longueur de la chaîne A.

Méthode efficace

Un moyen efficace de résoudre ce problème consiste à trouver la sous-séquence commune (LCS) la plus longue de deux chaînes. La longueur de la sous-chaîne la plus longue qui doit être supprimée dans la chaîne A pour qu'elle soit égale à la chaîne B est la différence entre la longueur de la chaîne A et la longueur du LCS.

Algorithme (efficace)

• Trouvez la sous-séquence commune (LCS) la plus longue de la chaîne A et de la chaîne B.

• Renvoie la différence entre la longueur de la chaîne A et la longueur du LCS.

Code C++ (efficace)

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

Sortie

Length of longest substring to be deleted: 1

Complexité temporelle (efficace) - O(m * n), où m est la longueur de la chaîne A et n est la longueur de la chaîne B.

Conclusion

Dans cet article, nous explorons le problème de trouver la longueur de la sous-chaîne la plus longue qui doit être supprimée pour rendre une chaîne égale à une autre. Nous discutons de méthodes simples mais efficaces pour résoudre ce problème, ainsi que de leur complexité algorithmique et temporelle. Les méthodes efficaces exploitent le concept de sous-séquence commune la plus longue et permettent d’obtenir des améliorations significatives en termes de complexité temporelle par rapport aux méthodes naïves.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!