資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告