C++ 给定二进制字符串的所有子字符串的异或

二进制字符串是只包含两种不同字符（’0’和’1’）的字符串。子字符串是通过从给定字符串的开头和结尾删除一些字符形成的字符串（可能是零个或全部）。我们给定一个字符串，并且我们要获取它的所有子字符串并进行异或运算。

异或是一种按位运算符，如果两个位相同，则返回0，否则返回1。

输入1

string str = "10101"

输出

XOR of all the substrings of the given binary string is: 11001

解释

对于最后一位，我们有三个设置位，所以为1；对于倒数第二位和倒数第三位，有两个设置位，意味着为0；而对于第一位和第二位，只有一个设置位。

输入2

string str = "111"

输出

110

方法

我们已经看过上面的例子了，现在让我们来处理实现部分：

• 首先，我们将创建一个函数，该函数将返回所需的字符串，并将给定的字符串作为参数。

• 在函数中，我们将获得字符串的大小，然后将值存储在表示当前位影响值的数组中。

• 当前位将对所有以其为零位置的子字符串有影响，在所有以其为第一、第二和第n位置的子字符串中，它将产生影响那么多次。

• 我们将遍历字符串并获取位，如果当前总位数为奇数，则将‘1’添加到结果中，否则添加‘0’。

• 最后，在主函数中返回最终答案并打印。

示例

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

// function to get the XOR it will return the required string 
string getXOR(string str){
   int len = str.size(); // size of the string     
   // array to store the how any number of times current bit will occures at any position 
   int arr[len]; 
   int tot = 0; // variable to store the total sum     
   // traversing over the array to get the number of ones can present at the given position 
   for (int i = 0; i < len; i++){
      if (str[i] == '1'){
         arr[i] = i + 1; 
      } else {
         arr[i] = 0; 
      }
   }
   // calculating nth bit total occurrences
   tot = accumulate(arr, arr + len, 0);    
   string res = "";
   for (int i = 0; i < len; i++){
      if(tot & 1){
         res = "1" + res;
      } else {
         res = "0" + res;
      }
      tot -= arr[len-1-i];
   }
   return res;
}
int main(){
   string str = "10101"; // given string     
   // calling to the function 
   cout<<"XOR of all the substrings of the given binary string is: "<<getXOR(str)<<endl;    
   return 0;
}

输出

XOR of all the substrings of the given binary string is: 11001

时间和空间复杂度

上述代码的时间复杂度是O(N)，其中N是给定字符串的大小。

上述代码的空间复杂度是线性的，即O(N)，因为我们使用了一个数组来存储每个位置的“1”的数量。

结论

在本教程中，我们实现了一个用于找到给定字符串所有子字符串的XOR的代码。子字符串是通过从给定字符串的开头和结尾删除一些字符形成的字符串（可能为零个或全部）。我们实现了一个具有线性时间复杂度的代码，即O(N)，并且具有相同的空间复杂度。