Đếm hoán vị xoay vòng có XOR với chuỗi nhị phân khác bằng 0 trong C++

Cho hai chuỗi nhị phân str_1 và str_2 chứa 0 và 1. Nhiệm vụ: tạo tập hợp "SET" các hoán vị khác nhau từ str_1, sau đó thực hiện XOR từng phần tử trong tập với str_2. Nếu kết quả XOR bằng 0 thì đếm, ngược lại bỏ qua.

Hiểu qua ví dụ

Ví dụ 1

Đầu vào: str_1 = "1111", str_2 = "1111"

Đầu ra: Số hoán vị xoay vòng thỏa mãn: 4

Giải thích: Tập hợp từ str_2 là {1111}. XOR với str_1: {1111} ^ "1111" = 0. Vì str_2 có 4 ký tự giống nhau nên tạo được 4 hoán vị khác nhau.

Ví dụ 2

Đầu vào: str_1 = "1101", str_2 = "1101"

Đầu ra: Số hoán vị xoay vòng thỏa mãn: 1

Giải thích: Tập hợp từ str_2: {1101, 1110, 1011, 0111}. XOR với str_1:

• {1101} ^ 1101 = 0
• {1110} ^ 1101 ≠ 0
• {1011} ^ 1101 ≠ 0
• {0111} ^ 1101 ≠ 0

Chỉ có 1 trường hợp XOR = 0.

Phương pháp sử dụng

• Nhập hai chuỗi nhị phân str_1, str_2 truyền vào cyclic_permutation().
• Gán str_2 = str_2 + str_2, sau đó str_2 = str_2.substr(0, str_2.size() - 1).
• Tạo chuỗi str = str_1 + "$" + str_2, tính độ dài, tạo mảng kích thước độ dài chuỗi.
• Gọi hàm check() với str và mảng.
• Trong check(): sử dụng thuật toán Z-function để tìm các vị trí khớp.
• Duyệt mảng kết quả, nếu arr[i] == str_1.length() tăng đếm.
• Trả về đếm và in kết quả.

Ví dụ mã nguồn

#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; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of cyclic permutations having XOR with other binary string as 0 are: 4