Maksimumkan fungsi yang diberikan dengan memilih subrentetan panjang yang sama daripada rentetan binari yang diberikan

Memandangkan dua rentetan binari str1 dan str2 yang sama panjang, kita perlu memaksimumkan nilai fungsi yang diberikan dengan memilih subrentetan daripada rentetan yang diberikan dengan panjang yang sama. Fungsi yang diberikan adalah seperti ini -

keseronokan(str1, str2) = (len(subrentetan))/(2^xor(sub1, sub2)).

Di sini, len(substring) ialah panjang subrentetan pertama dan xor(sub1, sub2) ialah XOR substring yang diberikan, ini mungkin kerana ia adalah rentetan binari.

Contoh

Input1: string str1 = 10110 & string str2 = 11101 

Output: 3

Arahan

Kita boleh memilih banyak set rentetan yang berbeza untuk mencari penyelesaian, tetapi memilih "101" daripada kedua-dua rentetan akan XOR sifar, yang akan menyebabkan fungsi mengembalikan nilai maksimum.

Input2: string str1 = 11111, string str2 = 10001 

Output: 1 

Arahan

Kita boleh memilih "1" sebagai subrentetan yang akan menghasilkan output ini dan jika kita memilih mana-mana rentetan lain ia akan menghasilkan nilai yang lebih rendah.

Kaedah naif

Dalam kaedah ini kita akan mencari semua subrentetan dan kemudian membandingkannya untuk mencari penyelesaian, tetapi penyelesaian ini tidak cekap dan memerlukan banyak masa dan kerumitan ruang.

Purata kerumitan masa untuk menghasilkan subrentetan panjang x ialah N^2, dan kemudian membandingkan setiap subrentetan akan menelan kos N^2 lebih. Selain itu, kita juga perlu mencari XOR subrentetan yang diberikan, yang juga menelan kos faktor tambahan N, yang bermaksud N^5 akan menjadi kerumitan masa kod di atas, yang sangat tidak cekap.

Kaedah yang cekap

Idea

Idea di sini datang daripada pemerhatian mudah bahawa apabila nilai XOR semakin tinggi, ia sentiasa mengurangkan jawapan. Oleh itu, untuk memaksimumkan nilai pulangan fungsi, kita mesti mengurangkan nilai XOR sebanyak mungkin.

Dalam kes di mana kedua-dua subrentetan adalah sifar, nilai XOR minimum yang boleh dicapai ialah sifar. Oleh itu, masalah ini sebenarnya berasal daripada masalah substring biasa yang paling lama.

Apabila XOR adalah sifar, bahagian dividen ialah 1, jadi jawapan akhir ialah panjang subrentetan sepunya terbesar.

Pelaksanaan

Kami telah melihat idea untuk menyelesaikan masalah, mari lihat langkah-langkah untuk melaksanakan kod -

• Kami akan mencipta fungsi yang akan menerima dua rentetan yang diberikan sebagai input dan mengembalikan nilai integer, yang akan menjadi hasil akhir kami.

• Dalam fungsi, kita mula-mula mendapatkan panjang rentetan dan kemudian mencipta vektor 2D dengan saiz yang didarab dengan rentetan yang diberikan.

• Kami akan menggunakan gelung bersarang untuk mengulang melalui rentetan dan mendapatkan subrentetan sepunya terbesar.

• Pada setiap lelaran kami akan menyemak sama ada indeks semasa dua rentetan sepadan dan kemudian kita akan mendapat nilai daripada vektor indeks terakhir kedua rentetan.

• Jika tidak, kami hanya akan menetapkan indeks semasa vektor kepada sifar.

• Selain itu, kami akan mengekalkan pembolehubah untuk mengekalkan kiraan panjang maksimum subrentetan biasa.

• Akhir sekali, kami akan mengembalikan jawapan dan mencetaknya dalam fungsi utama.

Contoh

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

Output

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

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N^2) kerana kami menggunakan bersarang untuk gelung dan berulang N kali setiap kali.

Memandangkan kami menggunakan tatasusunan dua dimensi untuk menyimpan elemen, kerumitan ruang kod di atas ialah O(N^2).

Kesimpulan

Dalam tutorial ini, kami mengekodkan untuk melaksanakan skor maksimum bagi fungsi tertentu dengan memilih subrentetan yang sama panjang daripada rentetan binari yang diberikan. Kami telah membincangkan pendekatan naif ini, yang sangat tidak cekap. Bergantung pada fungsi yang diberikan, nilai XOR adalah lebih kecil, jadi kami menjadikan XOR sifar dengan mendapatkan subrentetan sepunya terpanjang dalam kerumitan masa O(N^2).

Atas ialah kandungan terperinci Maksimumkan fungsi yang diberikan dengan memilih subrentetan panjang yang sama daripada rentetan binari yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!