Maximisez la fonction donnée en sélectionnant des sous-chaînes de longueur égale à partir de la chaîne binaire donnée

Étant donné deux chaînes binaires str1 et str2 de même longueur, nous devons maximiser la valeur de fonction donnée en sélectionnant des sous-chaînes parmi les chaînes données de même longueur. La fonction donnée est comme ceci -

fun(str1, str2) = (len(substring))/(2^xor(sub1, sub2)).

Ici, len(substring) est la longueur de la première sous-chaîne et xor(sub1, sub2) est le XOR de la sous-chaîne donnée, cela est possible puisqu'il s'agit de chaînes binaires.

Exemple

Input1: string str1 = 10110 & string str2 = 11101 

Output: 3

Instructions

Nous pourrions choisir de nombreux ensembles de chaînes différents pour trouver la solution, mais choisir "101" parmi les deux chaînes entraînera XOR zéro, ce qui amènera la fonction à renvoyer la valeur maximale.

Input2: string str1 = 11111, string str2 = 10001 

Output: 1 

Instructions

Nous pouvons sélectionner "1" comme sous-chaîne, ce qui entraînera cette sortie et si nous sélectionnons une autre chaîne, cela entraînera une valeur inférieure.

Méthode naïve

Dans cette méthode, nous trouverons toutes les sous-chaînes puis les comparerons pour trouver la solution, mais cette solution n'est pas efficace et prend beaucoup de temps et d'espace.

La complexité temporelle moyenne de la génération de sous-chaînes de longueur x est N^2, puis la comparaison de chaque sous-chaîne coûtera N^2 de plus. De plus, nous devons également trouver le XOR de la sous-chaîne donnée, ce qui coûte également un facteur supplémentaire de N, ce qui signifie que N^5 sera la complexité temporelle du code ci-dessus, ce qui est très inefficace.

Méthode efficace

Idées

L'idée ici vient de la simple observation selon laquelle à mesure que la valeur XOR augmente, la réponse diminue toujours. Par conséquent, afin de maximiser la valeur de retour de la fonction, nous devons réduire autant que possible la valeur XOR.

Dans le cas où les deux sous-chaînes sont nulles, la valeur XOR minimale pouvant être atteinte est zéro. Par conséquent, ce problème est en fait dérivé du problème de sous-chaîne commun le plus long.

Lorsque le XOR est nul, la partie dividende est 1, donc la réponse finale sera la longueur de la plus grande sous-chaîne commune.

Mise en œuvre

Nous avons vu l'idée pour résoudre le problème, regardons les étapes pour implémenter le code -

• Nous allons créer une fonction qui acceptera deux chaînes données en entrée et renverra une valeur entière, qui sera notre résultat final.

• Dans la fonction, nous obtenons d'abord la longueur de la chaîne, puis créons un vecteur 2D de la taille multipliée par la chaîne donnée.

• Nous utiliserons des boucles for imbriquées pour parcourir la chaîne et obtenir la plus grande sous-chaîne commune.

• À chaque itération, nous vérifierons si les indices actuels des deux chaînes correspondent, puis nous obtiendrons la valeur du vecteur du dernier index des deux chaînes.

• Sinon, nous définirions simplement l'indice actuel du vecteur à zéro.

• De plus, nous maintiendrons une variable pour maintenir un décompte de la longueur maximale de la sous-chaîne commune.

• Enfin, nous renverrons la réponse et l'imprimerons dans la fonction principale.

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to get the result
int result(string str1, string str2){
   int n = str1.length(); // size of the first string
   int m = str2.length(); // size of the second string   
   
   // creating vector to store the dynamic programming results 
   vector<vector<int>>dp(n+1, vector<int>(m+1)); 
   int ans = 0; // variable to store the result 
   
   // traversing over the strings using nested for loops 
   for (int i = 1; i <= n; i++){
      for (int j = 1; j <= m; j++){ 
      
         // if current elements of both the string are equal 
         if (str1[i - 1] == str2[j - 1]){
            // getting one maximum of the last two 
            dp[i][j] = 1 + dp[i - 1][j - 1];
            ans = max(ans, dp[i][j]);
         }
      }
   }
   return ans; // return the final answer or count 
} 
int main(){
   string str1 = "10110";
   string str2 = "11101"; 
   
   // calling the function
   cout<<"The maximum score for a given function by selecting equal length substrings from given binary strings is "<< result(str1,str2)<<endl;
   return 0;
}

Sortie

The maximum score for a given function by selecting equal length substrings from given binary strings is 3

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N^2) car nous utilisons des boucles for imbriquées et itérons N fois à chaque fois.

Puisque nous utilisons un tableau bidimensionnel pour stocker des éléments, la complexité spatiale du code ci-dessus est O(N^2).

Conclusion

Dans ce tutoriel, nous codons pour implémenter le score maximum d'une fonction donnée en sélectionnant des sous-chaînes de longueur égale à partir d'une chaîne binaire donnée. Nous avons déjà évoqué cette approche naïve et extrêmement inefficace. En fonction de la fonction donnée, la valeur du XOR est plus petite, nous rendons donc le XOR nul en obtenant la sous-chaîne commune la plus longue en complexité temporelle O(N^2).

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!