เราได้รับสตริงไบนารีสองสตริงคือ str_1 และ str_2 ที่ประกอบด้วย 1 และ 0 และภารกิจคือสร้างเซต "SET" ของการจัดเรียงที่แตกต่างกันที่เป็นไปได้จาก str_1 จากนั้นเราจะดำเนินการ XOR ของสมาชิกในเซตกับสตริงไบนารี str_2 และตรวจสอบว่า XOR คืนค่า 0 หรือไม่ ถ้าใช่ ให้นับกรณีนั้น มิฉะนั้นข้ามไป
ทำความเข้าใจด้วยตัวอย่าง
ตัวอย่าง
Input - string str_1 = "1111", string str_2 = "1111"
Output - จำนวนการจัดเรียงวนรอบที่ XOR กับสตริงไบนารีอีกอันได้ 0 คือ: 4
คำอธิบาย - เราจะสร้างเซตโดยใช้ str_2 และเซตจะเป็น {1111} ตอนนี้เราทำ XOR โดยใช้ str_1 และเซตที่สร้างขึ้น {1111} ^ "1111" = 0 เนื่องจากเรามีสมาชิก 4 ตัวที่เหมือนกันใน str_2 ดังนั้นเราสามารถสร้างการจัดเรียงที่แตกต่างกันได้ 4 แบบ ดังนั้นผลลัพธ์คือ 4
Input - string str_1 = "1101", string str_2 = "1101"
Output - จำนวนการจัดเรียงวนรอบที่ XOR กับสตริงไบนารีอีกอันได้ 0 คือ: 1
คำอธิบาย - เราจะสร้างเซตโดยใช้ str_2 และเซตจะเป็น {1101, 1110, 1011, 0111} ตอนนี้เราทำ XOR โดยใช้ str_1 และเซตที่สร้างขึ้น คือ
{1101} ^ 1101 = 0
{1110} ^ 1101 ไม่เท่ากับ 0
{1011} ^ 1101 ไม่เท่ากับ 0
{0111} ^ 1101 ไม่เท่ากับ 0
ตามที่เห็น เราได้ 0 เพียงครั้งเดียว ดังนั้นจำนวนนับคือ 1
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- รับสตริงไบนารีสองสตริง str_1 และ str_2 ส่งให้ฟังก์ชัน cyclic_permutation() ประมวลผลต่อ
- สร้างตัวแปรชั่วคราวเก็บผลลัพธ์ และตั้ง str_2 = str_2 + str_2 แล้ว str_2 = str_2.substr(0, str_2.size()-1)
- สร้างตัวแปร string str = str_1 + "$" + str_2 คำนวณความยาวของ str สร้างอาร์เรย์ขนาดความยาวของ str
- เรียกฟังก์ชัน check() ส่ง str และอาร์เรย์
- ภายในฟังก์ชัน
- ประกาศตัวแปร start และ end ตั้งค่าเป็น 0
- คำนวณความยาวของสตริง
- เริ่มลูป FOR จาก i = 1 ถึง len - 1 ตรวจสอบ IF i > end แล้ว start = i, end = เริ่ม WHILE end < len และ str[end-start] == str[end] เพิ่ม end ขึ้น 1
- ตั้ง arr[i] = end - start ลด end ลง 1
- Else สร้าง temp = i - start ตรวจสอบ IF arr[temp] < end - i + 1 แล้ว arr[i] = arr[temp] มิฉะนั้น start = i เริ่ม WHILE end < len และ str[end-start] == str[end] เพิ่ม end ตั้ง arr[i] = end - start ลด end ลง 1
- เริ่มลูป FOR จาก i = 1 ถึง len - 1 ตรวจสอบ IF arr[i] == str_1.length() เพิ่ม count ขึ้น 1
- คืนค่า count
- พิมพ์ผลลัพธ์
ตัวอย่าง
#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;
}
หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้
ผลลัพธ์
Count of cyclic permutations having XOR with other binary string as 0 are: 4
