เราได้รับด้วยสตริงไบนารีสองสตริง สมมติว่า str_1 และ str_2 ที่มีการรวมกันของ 1 และ 0 และงานคือการสร้างชุดก่อน สมมติว่า "SET" ของการเรียงสับเปลี่ยนที่เป็นไปได้จากสตริง str_1 จากนั้นเราจะดำเนินการ XOR ของ องค์ประกอบในชุดด้วยสตริงไบนารี str_2 จากนั้นตรวจสอบว่า XOR คืนค่า 0 หรือไม่ ถ้าใช่ ก็ถือว่ากรณีอื่นละเว้น
ให้เราเข้าใจด้วยตัวอย่าง
ตัวอย่าง
ป้อนข้อมูล - string str_1 ="1111", string str_2 ="1111"
ผลลัพธ์ - จำนวนการเรียงสับเปลี่ยนแบบวนรอบที่มี XOR กับสตริงไบนารีอื่นๆ เป็น 0 คือ:4
คำอธิบาย - เราจะสร้างชุดโดยใช้สตริง str_2 และชุดจะเป็น {1111} ตอนนี้เราจะดำเนินการ XOR โดยใช้สตริง str_1 และตั้งค่ารูปแบบดังนั้น {1111} ^ “1111” =0 เนื่องจากเรามีองค์ประกอบที่คล้ายกัน 4 รายการในสตริง str_2 เราจึงสร้างการเรียงสับเปลี่ยนได้ 4 แบบ ดังนั้นผลลัพธ์จึงเป็น 4
ป้อนข้อมูล - string str_1 ="1101", string str_2 ="1101"
ผลลัพธ์ - จำนวนการเรียงสับเปลี่ยนแบบวนรอบที่มี 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)
- สร้างตัวแปรประเภทสตริง str และตั้งค่าเป็นการรวมกันของ str_1 และ str_2 จากนั้นคำนวณความยาวของสตริง str สร้างอาร์เรย์ของความยาวของสตริง str.
- เรียกใช้ฟังก์ชัน check() โดยส่งสตริง str และ array ไปยังฟังก์ชันเป็นอาร์กิวเมนต์
- ภายในฟังก์ชัน
- ประกาศตัวแปรสองตัวเริ่มต้นและสิ้นสุดและตั้งค่าเป็น 0
- คำนวณความยาวของสตริง
- เริ่มวนรอบ FOR จาก i จนถึงความยาวสำหรับ string -1 และตรวจสอบว่า i มากกว่า end แล้วตั้งค่า start เป็น i และสิ้นสุดเป็น i ตอนนี้เริ่มต้นในขณะที่สิ้นสุดน้อยกว่าความยาวของสตริงและ str[end-start] เท่ากับ str[end] และเพิ่มค่าของการสิ้นสุดโดย 1
- ตั้งค่า arr[i] เป็น end - เริ่มและลดจุดสิ้นสุดทีละ 1
- มิฉะนั้น ให้สร้างตัวแปรชั่วคราว temp และตั้งค่าเป็น i - start และตรวจสอบว่า arr[temp] น้อยกว่า end - i + 1 จากนั้นตั้งค่า arr[i] เป็น arr[temp] มิฉะนั้น ให้ตั้งค่าเริ่มต้นเป็น i และเริ่มต้นในขณะที่สิ้นสุดน้อยกว่าความยาวของสตริงและ str[end-start] เป็น str[end] จากนั้นเพิ่มจุดสิ้นสุดขึ้น 1 และตั้งค่า arr[i] เป็นสิ้นสุด - เริ่มและลดจุดสิ้นสุดทีละ 1 .
- เริ่มลูป FOR จาก i ถึง 1 จนถึงความยาวของสตริง str -1 และตรวจสอบว่า arr[i] เท่ากับความยาวของสตริง str_1 แล้วเพิ่มจำนวนขึ้น 1
- จำนวนคืน
- พิมพ์ผลลัพธ์
ตัวอย่าง
#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
