Maison > développement back-end > C++ > 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

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Libérer: 2023-09-16 17:53:06
avant
858 Les gens l'ont consulté

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;
}
Copier après la connexion

Sortie

Length of longest substring to be deleted: 1
Copier après la connexion
Copier après la connexion

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;
}
Copier après la connexion

Sortie

Length of longest substring to be deleted: 1
Copier après la connexion
Copier après la connexion

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!

Étiquettes associées:
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal