C++ 给定二进制字符串的任意两个子字符串的最大按位或

在这个问题中，我们需要找到给定字符串的任意两个子字符串的最大OR值。

第一种方法是找到给定二进制字符串的所有子字符串，对每个字符串进行OR运算，并打印出最大的OR值。

另一种方法是将原始字符串作为一个子字符串，从最左边的零开始取另一个子字符串以使OR值最大化。

问题陈述 -我们给定了一个二进制字符串alpha。我们需要找到给定二进制字符串的任意两个子字符串的最大OR值。

样例示例

输入

alpha = "1000010"

输出结果

1100011

解释 - 第一个子字符串是 ‘1000010’，另一个子字符串是 ‘000010’。当我们取这两个子字符串的OR值时，得到 ‘1100011’。

输入

alpha = "1111";

输出结果

1111

解释 - 字符串已经是最大的。所以，我们可以取一个原始字符串和任何其他子字符串来得到最大的结果。

输入

alpha = "1100";

输出

1111

解释 - 我们可以取1100和11的子字符串来得到最大结果。

方法1

在这个方法中，我们将所有给定二进制字符串的子字符串存储在列表中。之后，我们将对每个子字符串进行OR操作并跟踪最大值。同时，我们将创建一个函数来比较两个子字符串并进行OR操作。

算法

步骤1 - 将’maxOR’字符串变量初始化为空字符串以存储任意两个字符串的最大OR值。同时，定义subStr列表以存储所有子字符串。

步骤2 - 遍历给定的二进制字符串，使用substr()方法取得所有可能的子字符串，并压入subStr列表中。substr()方法需要起始索引作为第一个参数，子字符串的长度作为第二个参数。

步骤3 - 开始遍历子字符串列表。同时，使用嵌套循环遍历其他子字符串以将当前子字符串与其他子字符串进行OR操作。

步骤4 - 执行takeOR()函数来进行两个字符串的OR操作。

步骤4.1 - 如果temp1字符串的长度小于temp2的长度，在temp1字符串前追加初始零。否则，在temp2字符串前追加初始零。

步骤4.2 - 将’res’字符串初始化为空字符串以存储结果的OR值。

步骤4.3 - 遍历temp1和temp2两个字符串。如果任何一个字符串在当前索引处包含’1’，则将’1’附加到’res’字符串。否则，将’0’附加到’res’字符串。

步骤4.4 - 返回’res’字符串。

步骤5 - 在获得OR值之后，通过执行getmax()函数检查OR值是否大于maxOR字符串值。

步骤5.1 - 如果temp1的大小大于temp2，则返回temp1。同样地，如果temp2的大小大于temp1，则返回temp1。

步骤5.2 - 开始遍历字符串。

步骤5.3 - 如果第p个索引处的字符在temp1中更大，则返回temp1。同样地，如果在temp2中的第p个索引处的字符更大，则返回temp2。

步骤5.4 - 最后，返回’temp1’字符串。

步骤6 - 将getMax()函数返回的值存储在’maxOR’变量中。

步骤7 - 返回’maxOR’变量的值。

示例

#include <bits/stdc++.h>
using namespace std;

string takeOR(string &temp1, string &temp2) {
   // If the string length is not equal, then add 0's at the start of smaller string
   if (temp1.size() < temp2.size()) {
      int diff = temp2.size() - temp1.size();
      for (int p = 0; p < diff; p++) {
         temp1 = '0' + temp1;
      }
   } else if (temp1.size() > temp2.size()) {
      int diff = temp1.size() - temp2.size();
      for (int p = 0; p < diff; p++) {
         temp2 = '0' + temp2;
      }
   }

   string res = "";
   // Take OR of both strings
   for (int p = 0; p < temp1.length(); p++) {
      if (temp1[p] == '1' || temp2[p] == '1') {
         res += '1';
      } else {
         res += '0';
      }
   }
   return res;
}

string getMax(string temp1, string temp2) {
   // Return large string if the size is not equal
   if (temp1.size() > temp2.size()) {
      return temp1;
   } else if (temp1.size() < temp2.size()) {
      return temp2;
   }

   // Compare two strings and return the maximum string
   for (int p = 0; p < temp1.size(); p++) {
      if (temp1[p] > temp2[p]) {
         return temp1;
      } else if (temp1[p] < temp2[p]) {
         return temp2;
      }
   }
   return temp1;
}

string maxORVal(string alpha) {
   string maxOR = "";
   vector<string> subStr;
   // get all substrings of the given string
   for (int p = 0; p < alpha.length(); p++) {
      for (int q = 1; q <= alpha.length() - p; q++) {
         subStr.push_back(alpha.substr(p, q));
      }
   }

   // Get the maximum OR value of two substrings
   for (int p = 0; p < subStr.size(); p++) {
      for (int q = p + 1; q < subStr.size(); q++) {
         // Take OR of two strings
         string OR_res = takeOR(subStr[p], subStr[q]);
         // Get maximum string
         maxOR = getMax(maxOR, OR_res);
      }
   }
   return maxOR;
}

int main() {
   string alpha = "1000010";
   cout << "The maximum OR value of any two substrings of the given string  is " << maxORVal(alpha);
   return 0;
}

输出

The maximum OR value of any two substrings of the given string is 1100011

时间复杂度 – O（N * N * N），其中O（N * N）是为了遍历所有的子字符串，O（N）是为了找到最大值并对两个字符串进行OR运算。

空间复杂度 – O（N * N）用于存储所有子字符串。

方法2

在这个方法中，我们从最左边的0开始取子字符串，将其与原始字符串进行OR运算，这将始终给出最大值。

算法

步骤 1 - 使用空字符串初始化 ‘temp1’ 和 ‘temp2’ 字符串，用于存储临时字符串。

步骤 2 - 接下来，我们需要从原始字符串中去除前导零。开始遍历字符串，当找到第一个 ‘1’ 时，从该索引处取子字符串，并将子字符串存储在 ‘temp1’ 中。

步骤 3 - 如果 p 等于字符串长度，则返回 ‘0’，因为字符串包含全部为零。

步骤 4 - 开始遍历字符串，并将当前字符附加到 ‘temp2’ 字符串。如果当前字符为 ‘0’，将索引值存储在 ‘x’ 中，并打破循环，因为我们需要从最左边的零开始取子字符串。

步骤 5 - 如果 x 等于 ‘temp1’ 字符串的长度，则返回 temp2 字符串，因为它包含全部为1。

步骤 6 - 再次遍历字符串，进行原始字符串和从最左边零开始的子字符串的OR运算。

步骤 7 - 如果 temp1[p] 或 temp1[x] 等于 ‘1’，将 ‘1’ 附加到 temp2。否则，将 ‘0’ 附加到 temp2。

步骤 8 - 最后，返回 ‘temp2’ 字符串。

示例

#include <bits/stdc++.h>
using namespace std;

string maxORVal(string alpha) {
   int p, q, len = alpha.length();
   string temp1 = "", temp2 = "";
   // Removing leading zeros from the string
   for (p = 0; p < len; p++) {
     if (alpha[p] == '1') {
       // Get substring from p to len
       temp1 = alpha.substr(p, len);
       break;
     }
   }
   // For a string containing all zeros, the answer is '0'.
   if (p == len) {
     return "0";
   }
   int x, temp1_len = temp1.size();
   // Get substring from start to first zero
   for (x = 0; x < temp1_len; x++) {
     if (temp1[x] == '0') {
       break;
     }
     temp2 += temp1[x];
   }
   // If the string contains all ones, the answer is '1'.
   if (x == temp1_len)
     return temp2;
   // Get maximum OR value
   for (p = 0; p < temp1_len and x < temp1_len; p++, x++) {
     if (temp1[p] == '1' or temp1[x] == '1')
       temp2 += '1';
     else
       temp2 += '0';
   }
   // Return the answer
   return temp2;
}
int main() {
   string alpha = "1000010";
   cout << "The maximum OR value of any two substrings of the given string  is " << maxORVal(alpha);
   return 0;
}

输出

The maximum OR value of any two substrings of the given string is 1100011

时间复杂度 – O(N) 一次遍历字符串。

空间复杂度 – O(N) 存储子字符串。

第二种方法是对第一种方法的优化版本。在第二种方法中，我们将从最左边的零开始的子字符串视为另一个子字符串，因为每当将其与原始字符串进行OR运算时，它总是给出最大值。