数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学给定二进制字符串的所有子串的异或
二进制字符串是指只包含两种不同字符（'0'和'1'）的字符串。子串是从给定字符串开头和结尾删除一些字符（可能为零个或所有字符）形成的字符串。给定一个字符串，我们需要获取所有子串并进行异或运算。
异或是一个按位运算符，其结果如下：如果两个位相同，则返回零；否则返回1。
输入
string str = "10101"
输出
XOR of all the substrings of the given binary string is: 11001
解释
对于最后一位，我们有三位被设置为1，所以结果为1；对于倒数第二位和倒数第三位，有两位置为1，这意味着结果为0；对于第一位和第二位，只有一位置为1。
输入
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)，因为我们使用数组来存储每个位置一的计数。
结论
在本教程中，我们实现了一个代码来查找给定字符串所有子串的异或。子串是从给定字符串开头和结尾删除一些字符（可能为零个或所有字符）形成的字符串。我们实现的代码具有线性时间复杂度O(N)和相同空间复杂度。
更新于：2023年8月24日
202 次浏览
广告