透過從給定的二進位字串中選擇相等長度的子字串，最大化給定函數

給定兩個相同長度的二進位字串str1 和str2，我們必須透過從給定的相同長度的字串中選擇子字串來最大化給定的函數值。給定的函數是這樣的 -

fun(str1, str2) = (len(子字串))/(2^xor(sub1, sub2))。

這裡，len(substring) 是第一個子字串的長度，而 xor(sub1, sub2) 是給定子字串的異或，因為它們是二進位字串，所以這是可能的。

範例

Input1: string str1 = 10110 & string str2 = 11101 

Output: 3

說明

我們可以選擇許多不同的字串集來找到解決方案，但從兩個字串中選擇「101」將使異或為零，這將導致函數傳回最大值。

Input2: string str1 = 11111, string str2 = 10001 

Output: 1 

說明

我們可以選擇「1」作為子字串，這將導致此輸出，如果我們選擇任何其他字串，則會產生較低的值。

天真的方法

在這種方法中，我們將找到所有子字串，然後比較它們以找到解決方案，但這種解決方案效率不高，並且會花費大量時間和空間複雜度。

產生長度 x 平均時間複雜度的子字串是 N^2，然後比較每個子字串將花費 N^2 多。另外，我們還必須找到給定子字串的異或，這也會花費額外的 N 因子，這意味著 N^5 將是上述程式碼的時間複雜度，效率非常低。

高效的方法

想法

這裡的想法來自於一個簡單的觀察，即隨著異或值變高，它總是會減少答案。因此，為了最大化函數傳回值，我們必須盡可能減少異或值。

在兩個子字串都為零的情況下，可以實現的最小 XOR 值為零。所以，這個問題其實是由最長的公共子串問題衍生出來。

當異或為零時，被除數部分為1，因此最終答案將是最大公共子字串的長度。

實作

我們已經看到了解決問題的想法，讓我們看看實現程式碼的步驟 -

• 我們將建立一個函數，它將接受兩個給定的字串作為輸入並傳回整數值，這將是我們的最終結果。

• 在函數中，我們首先取得字串的長度，然後建立一個與給定字串相乘的大小的二維向量。

• 我們將使用巢狀的 for 迴圈來遍歷字串並取得最大的公共子字串。

• 在每次迭代時，我們將檢查兩個字串的當前索引是否匹配，然後我們將從兩個字串的最後一個索引的向量中取得值。

• 否則，我們只會將向量的目前索引設為零。

• 此外，我們將維護一個變數來維護公共子字串最大長度的計數。

• 最後，我們將返回答案並在主函數中列印它。

範例

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

輸出

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

時間與空間複雜度

#上述程式碼的時間複雜度為 O(N^2)，因為我們使用巢狀的 for 循環，每次迭代 N 次。

由於我們使用二維數組來儲存元素，因此上述程式碼的空間複雜度為 O(N^2)。

結論

在本教程中，我們透過從給定的二進位字串中選擇等長的子字串來實現給定函數的最大分數的程式碼。我們已經討論過這種幼稚的方法，這種方法效率極低。根據給定的函數，異或的值越小，因此我們透過在O(N^2)時間複雜度內取得最長公共子字串來使異或為零。

以上是透過從給定的二進位字串中選擇相等長度的子字串，最大化給定函數的詳細內容。更多資訊請關注PHP中文網其他相關文章！