Maximieren Sie die angegebene Funktion, indem Sie Teilzeichenfolgen gleicher Länge aus der angegebenen Binärzeichenfolge auswählen

Gegeben zwei Binärzeichenfolgen str1 und str2 gleicher Länge, müssen wir den gegebenen Funktionswert maximieren, indem wir Teilzeichenfolgen aus den gegebenen Zeichenketten gleicher Länge auswählen. Die angegebene Funktion sieht so aus -

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

Hier ist len(substring) die Länge des ersten Teilstrings und xor(sub1, sub2) das XOR des gegebenen Teilstrings. Dies ist möglich, da es sich um binäre Strings handelt.

Beispiel

Input1: string str1 = 10110 & string str2 = 11101 

Output: 3

Anleitung

Wir könnten viele verschiedene Sätze von Zeichenfolgen auswählen, um die Lösung zu finden, aber die Auswahl von „101“ aus beiden Zeichenfolgen führt zu einer XOR-Nullung, was dazu führt, dass die Funktion den Maximalwert zurückgibt.

Input2: string str1 = 11111, string str2 = 10001 

Output: 1 

Anleitung

Wir können „1“ als Teilzeichenfolge auswählen, was zu dieser Ausgabe führt, und wenn wir eine andere Zeichenfolge auswählen, führt dies zu einem niedrigeren Wert.

Naive Methode

Bei dieser Methode finden wir alle Teilzeichenfolgen und vergleichen sie dann, um die Lösung zu finden. Diese Lösung ist jedoch nicht effizient und erfordert viel Zeit und Platzkomplexität.

Die durchschnittliche Zeitkomplexität für die Generierung von Teilzeichenfolgen der Länge x beträgt N^2, und der anschließende Vergleich jeder Teilzeichenfolge kostet N^2 mehr. Darüber hinaus müssen wir auch das XOR des gegebenen Teilstrings finden, was ebenfalls einen zusätzlichen Faktor N kostet, was bedeutet, dass N^5 die zeitliche Komplexität des obigen Codes ist, was sehr ineffizient ist.

Effiziente Methode

Ideen

Die Idee hier beruht auf der einfachen Beobachtung, dass die Antwort immer kleiner wird, wenn der XOR-Wert höher wird. Um den Rückgabewert der Funktion zu maximieren, müssen wir daher den XOR-Wert so weit wie möglich reduzieren.

In dem Fall, dass beide Teilzeichenfolgen Null sind, ist der minimal erreichbare XOR-Wert Null. Daher leitet sich dieses Problem tatsächlich vom Problem der längsten gemeinsamen Teilzeichenfolge ab.

Wenn das XOR Null ist, ist der Dividendenteil 1, sodass die endgültige Antwort die Länge des größten gemeinsamen Teilstrings ist.

Umsetzung

Wir haben die Idee zur Lösung des Problems gesehen, schauen wir uns die Schritte zur Implementierung des Codes an -

• Wir erstellen eine Funktion, die zwei gegebene Zeichenfolgen als Eingabe akzeptiert und einen ganzzahligen Wert zurückgibt, der unser Endergebnis sein wird.

• In der Funktion ermitteln wir zunächst die Länge der Zeichenfolge und erstellen dann einen 2D-Vektor mit der Größe multipliziert mit der angegebenen Zeichenfolge.

• Wir werden verschachtelte for-Schleifen verwenden, um die Zeichenfolge zu durchlaufen und die größte gemeinsame Teilzeichenfolge zu erhalten.

• Bei jeder Iteration prüfen wir, ob die aktuellen Indizes der beiden Zeichenfolgen übereinstimmen, und erhalten dann den Wert aus dem Vektor des letzten Index beider Zeichenfolgen.

• Andernfalls würden wir den aktuellen Index des Vektors einfach auf Null setzen.

• Darüber hinaus werden wir eine Variable verwalten, um die maximale Länge des gemeinsamen Teilstrings zu zählen.

• Abschließend geben wir die Antwort zurück und drucken sie in der Hauptfunktion aus.

Beispiel

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

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N^2), da wir verschachtelte for-Schleifen verwenden und jedes Mal N-mal iterieren.

Da wir ein zweidimensionales Array zum Speichern von Elementen verwenden, beträgt die räumliche Komplexität des obigen Codes O(N^2).

Fazit

In diesem Tutorial erstellen wir Code, um die maximale Punktzahl einer bestimmten Funktion zu implementieren, indem wir Teilzeichenfolgen gleicher Länge aus einer bestimmten Binärzeichenfolge auswählen. Wir haben diesen naiven Ansatz, der äußerst ineffizient ist, bereits besprochen. Abhängig von der gegebenen Funktion ist der Wert des XOR kleiner, daher machen wir das XOR auf Null, indem wir den längsten gemeinsamen Teilstring in der Zeitkomplexität O(N^2) erhalten.

Das obige ist der detaillierte Inhalt vonMaximieren Sie die angegebene Funktion, indem Sie Teilzeichenfolgen gleicher Länge aus der angegebenen Binärzeichenfolge auswählen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!