從給定的二進位制字串中選擇等長子字串，最大化給定函式

---

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

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

這裡，子字串長度是第一個子字串的長度，而 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 將是上述程式碼的時間複雜度，這非常低效。

高效方法

思路

這裡的思路來自於一個簡單的觀察結果：隨著異或值變高，它總是會降低答案。因此，為了最大化函式的返回值，我們必須儘可能地降低異或值。

可以達到的最小異或值為零，當兩個子字串都為零時。因此，這個問題實際上是從“最長公共子字串”問題派生出來的。

當異或為零時，被除數部分為 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)，因為我們使用了每個迴圈迭代 N 次的巢狀 for 迴圈。

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

結論

在本教程中，我們實現了從給定的二進位制字串中選擇等長子字串以最大化給定函式分數的程式碼。我們討論了樸素方法，它效率非常低。根據給定的函式，異或越小，值越大，因此我們將透過在 O(N^2) 時間複雜度內獲取最長公共子字串來使異或結果為零。