বাইনারি স্ট্রিংর XOR ০ হলে সাইক্লিক পারমুটেশনের সংখ্যা গণনা (C++)

দুটি বাইনারি স্ট্রিং str_1 এবং str_2 দেওয়া আছে যাতে ০ এবং ১ এর কম্বিনেশন রয়েছে। কাজ হল প্রথমে str_1- থেকে সম্ভাব্য সব সাইক্লিক পারমুটেশন বানানো (সেট "SET"), তারপর সেটের প্রতিটি এলিমেন্টের সাথে str_2-র XOR অপারেশন করা। যদি XOR ফলাফল ০ হয় তবে সেটি গণনা করুন।

উদাহরণ দিয়ে বোঝা যাক

উদাহরণ ১

ইনপুট - string str_1 = "1111", string str_2 = "1111"

আউটপুট - XOR ০ হলে সাইক্লিক পারমুটেশনের সংখ্যা: 4

ব্যাখ্যা - str_2 দিয়ে সেট বানানো হলো {1111}। এখন str_1 দিয়ে XOR: {1111} ^ "1111" = 0। str_2-তে ৪টি একই এলিমেন্ট রয়েছে তাই ৪টি পারমুটেশন সম্ভব।

উদাহরণ ২

ইনপুট - string str_1 = "1101", string str_2 = "1101"

আউটপুট - XOR ০ হলে সাইক্লিক পারমুটেশনের সংখ্যা: 1

ব্যাখ্যা - str_2 দিয়ে সেট: {1101, 1110, 1011, 0111}। str_1 দিয়ে XOR:

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

শুধু একটি ০ পাওয়া গেলে, তাই কাউন্ট ১।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

• দুটি বাইনারি স্ট্রিং ইনপুট নিয়ে cyclic_permutation() ফাংশনে পাস করুন।
• টেম্পোরারি ভেরিয়েবল দিয়ে ফলাফল সংরক্ষণ করুন। str_2 = str_2 + str_2 করুন, তারপর str_2 = str_2.substr(0, str_2.size()-1)।
• স্ট্রিং str = str_1 + "$" + str_2 বানান এবং এর দৈর্ঘ্য নিয়ে অ্যারে তৈরি করুন।
• check() ফাংশন কল করুন স্ট্রিং এবং অ্যারে পাস করে।
• check() ফাংশনে:
  • start=0, end=0।
  • স্ট্রিং দৈর্ঘ্য নিয়ে i=1 থেকে len-1 পর্যন্ত লুপ।
  • যদি i > end হয় তবে start=i, end=i। হোয়াইল লুপে str[end-start] == str[end] চেক করে end++। arr[i] = end-start, end--।
  • অন্যথায় temp = i-start। যদি arr[temp] < end-i+1 হয় তবে arr[i] = arr[temp], অন্যথায় start=i করে হোয়াইল লুপ চালান এবং arr[i] = end-start, end--।
• i=1 থেকে len-1 পর্যন্ত লুপে যদি arr[i] == str_1.length() হয় তবে কাউন্ট বাড়ান।
• কাউন্ট রিটার্ন করুন এবং প্রিন্ট করুন।

উদাহরণ কোড

#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