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

给定两个长度相同的二进制字符串str1和str2，我们要通过选择相等长度的子字符串从给定的字符串中来最大化给定函数的值。给定函数是这样的 −

fun(str1, str2) = (len(substring))/(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，所以最终答案将是最大公共子字符串的长度。

实现

我们已经看到了解决这个问题的思路，让我们看一下实现代码的步骤−

• 我们将创建一个函数，该函数将获取两个给定的字符串作为输入，并返回整数值，这将是我们的最终结果。

• 在函数中，首先，我们将获取字符串的长度，然后我们将创建一个大小为给定字符串乘法的2-D向量。

• 我们将使用嵌套的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次迭代。

以上代码的空间复杂度为O(N^2)，因为我们使用了一个二维数组来存储元素。

结论

在本教程中，我们实现了一个给定函数的最大得分代码，通过从给定的二进制字符串中选择相等长度的子字符串。我们讨论了朴素的方法，该方法效率非常低。根据给定的函数，异或值越小，值越高，所以我们将在O(N^2)的时间复杂度内获取最长公共子字符串，使异或结果为零。