Chúng tôi được cung cấp với hai chuỗi nhị phân, giả sử str_1 và str_2 chứa sự kết hợp của 1 và 0 và nhiệm vụ trước tiên là tạo thành tập hợp, giả sử "SET" của các hoán vị khác nhau có thể từ chuỗi str_1 và sau đó chúng tôi sẽ thực hiện các phép toán XOR của các phần tử trong bộ với chuỗi nhị phân str_2 và sau đó kiểm tra xem XOR có trả về 0 hay không. Nếu có, hãy xem xét trường hợp khác, bỏ qua nó.
Hãy cho chúng tôi hiểu với các ví dụ.
Ví dụ
Đầu vào - chuỗi str_1 ="1111", chuỗi str_2 ="1111"
Đầu ra - Số hoán vị tuần hoàn có XOR với chuỗi nhị phân khác là 0 là:4
Giải thích - Chúng tôi sẽ tạo tập hợp bằng cách sử dụng chuỗi str_2 và tập hợp sẽ là {1111}. Bây giờ chúng ta sẽ thực hiện các phép toán XOR bằng cách sử dụng chuỗi str_1 và tập hợp được tạo thành {1111} ^ “1111” =0. Vì chúng ta có 4 phần tử giống nhau trong chuỗi str_2 nên chúng ta có thể tạo thành 4 hoán vị khác nhau do đó đầu ra là 4.
Đầu vào - chuỗi str_1 ="1101", chuỗi str_2 ="1101"
Đầu ra - Số hoán vị tuần hoàn có XOR với chuỗi nhị phân khác là 0 là:1
Giải thích - Chúng tôi sẽ tạo tập hợp bằng cách sử dụng chuỗi str_2 và tập hợp sẽ là {1101, 1110, 1011, 0111}. Bây giờ chúng ta sẽ thực hiện các hoạt động XOR bằng cách sử dụng chuỗi str_1 và thiết lập được hình thành, tức là
{1101} ^ 1101 =0
{1110} ^ 1101 không bằng 0
{1011} ^ 1101 không bằng 0
{0111} ^ 1101 không bằng 0
Như chúng tôi có thể, chúng tôi chỉ đạt được một số 0 do đó số lượng là 1.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
- Nhập hai chuỗi nhị phân, giả sử str_1 và str_2 và chuyển chúng đến hàm cyclic_permutation () để xử lý thêm.
- Tạo một biến tạm thời để lưu trữ kết quả và đặt str_2 là str_2 + str_2, sau đó đặt str_2 là str_2.substr (0, str_2.size () - 1).
- Tạo một biến kiểu chuỗi str và đặt nó thành sự kết hợp của str_1 và str_2, sau đó tính độ dài của chuỗi str. Tạo một mảng có độ dài bằng chuỗi str.
- Gọi hàm check () bằng cách chuyển chuỗi str và mảng cho hàm dưới dạng đối số.
- Bên trong hàm
- Khai báo hai biến bắt đầu và kết thúc và đặt chúng thành 0
- Tính độ dài của chuỗi.
- Bắt đầu vòng lặp FOR từ i cho đến độ dài cho chuỗi -1 và kiểm tra NẾU i lớn hơn kết thúc, sau đó đặt bắt đầu là i và kết thúc là i. Bây giờ hãy bắt đầu Trong khi kết thúc nhỏ hơn độ dài của chuỗi AND str [end-start] bằng str [end] và tăng giá trị của end lên 1
- Bây giờ đặt arr [i] là end - bắt đầu và giảm dần đến cuối 1
- Nếu không, hãy tạo một biến tạm thời tạm thời và đặt nó là i - start và kiểm tra IF arr [temp] nhỏ hơn end - i + 1, sau đó đặt arr [i] là arr [temp]. Ngược lại, đặt start thành i và bắt đầu WHILE kết thúc nhỏ hơn độ dài của chuỗi AND str [end-start] là str [end] sau đó tăng phần cuối bằng 1 và đặt arr [i] là end - bắt đầu và giảm phần cuối bằng 1 .
- Bắt đầu vòng lặp FOR từ i đến 1 cho đến khi độ dài của chuỗi str -1 và kiểm tra IF arr [i] bằng độ dài của chuỗi str_1 rồi tăng số lượng lên 1
- Số lượt trả lại
- In kết quả
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void check(string str, int arr[]) {
int start = 0, end = 0;
int len = str.length();
for (int i = 1; i <= len - 1; i++) {
if (i > end) {
start = i;
end = i;
while (end < len && str[end - start] == str[end]) {
end++;
}
arr[i] = end - start;
end--;
} else {
int temp = i - start;
if (arr[temp] < end - i + 1) {
arr[i] = arr[temp];
} else {
start = i;
while (end < len && str[end - start] == str[end]) {
end++;
}
arr[i] = end - start;
end--;
}
}
}
}
int cyclic_permutation(string str_1, string str_2) {
int count = 0;
str_2 = str_2 + str_2;
str_2 = str_2.substr(0, str_2.size() - 1);
string str = str_1 + "$" + str_2;
int len = str.length();
int arr[len];
check(str, arr);
for (int i = 1; i <= len - 1; i++) {
if (arr[i] == str_1.length()) {
count++;
}
}
return count;
}
int main() {
string str_1 = "1111";
string str_2 = "1111";
cout << "Count of cyclic permutations having XOR with other binary string as 0 are: " << cyclic_permutation(str_1, str_2);
return 0;
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count of cyclic permutations having XOR with other binary string as 0 are: 4