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

给定两个相同长度的二进制字符串 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中文网其他相关文章！