从给定的二进制字符串中选择等长子字符串，最大化给定函数

---

给定两个相同长度的二进制字符串 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) 时间复杂度内获取最长公共子字符串来使异或结果为零。