দুটি স্ট্রিংয়ের সাধারণ ভাজক সংখ্যা গণনা C++-এ

দুটি স্ট্রিং numo এবং demo ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হলো উভয় স্ট্রিংয়ের সাধারণ ভাজক (common divisors) সংখ্যা বের করা। একটি স্ট্রিং str-এর ভাজক sub1 হলো এমন সাবস্ট্রিং যাكرر করে str তৈরি করা যায়। উদাহরণ: str=abcabcabc, sub1=abc।

ইনপুট

numo = "abababab" demo = "abababababababab"

আউটপুট

Count of number of common divisors of the given strings are: 2

ব্যাখ্যা

স্ট্রিংগুলো নিচের ভাজক সাবস্ট্রিং দিয়ে জেনারেট করা যায়: "ab", "abab"

ইনপুট

numo = "pqqppqqp" demo = "pqpq"

আউটপুট

Count of number of common divisors of the given strings are: 0

ব্যাখ্যা

স্ট্রিংয়দের কোনো সাধারণ ভাজক নেই। শুধু ভাজকগুলো: numo-এর জন্য "pqqp" এবং demo-এর জন্য "pq"।

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

যেকোনো স্ট্রিং sub1 যদি str-এর ভাজক হয় তবে সেটি অবশ্যই str-এর প্রিফিক্স হবে এবং এর দৈর্ঘ্য str-এর দৈর্ঘ্যকে সম্পূর্ণ ভাগ করবে। এই শর্ত sub1-এর সাথে উভয় স্ট্রিং numo এবং demo দিয়ে চেক করে কাউন্ট বাড়ানো হয়।

• স্ট্রিং numo এবং demo ইনপুট নেওয়া হয়।
• verify(string str, int val) ফাংশন স্ট্রিং এবং ভ্যালু নিয়ে সাবস্ট্রিং ০ থেকে val повтор করে str তৈরি করা যায় কিনা চেক করে (১/০ রিটার্ন)।
• common_divisor(string numo, string demo) ফাংশন দুটি স্ট্রিং নিয়ে সাধারণ ভাজকের কাউন্ট রিটার্ন করে।
• ইনিশিয়াল কাউন্ট ০।
• ইনপুট স্ট্রিংদের দৈর্ঘ্য নির্ণয় করে ন্যূনতম দৈর্ঘ্য min_val-এ স্টোর।
• ফর লুপ i=0 থেকে min_val পর্যন্ত।
• যদি করেন্ট দৈর্ঘ্য i উভয় স্ট্রিং দৈর্ঘ্যকে ভাগ করে এবং প্রিফিক্স মিলে যায় numo.substr(0, i) == demo.substr(0, i)।
• তবে verify() দিয়ে চেক করা হয় সাবস্ট্রিং ০ থেকে i উভয় স্ট্রিংয়ের ভাজক কিনা।
• উভয় verify ১ রিটার্ন করলে count++।
• ফর লুপ শেষে count রিটার্ন।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int verify(string str, int val) {
    int length = str.length();
    for (int i = 0; i < length; i++) {
        if (str[i] != str[i % val]) {
            return 0;
        }
    }
    return 1;
}

int common_divisor(string numo, string demo) {
    int count = 0;
    int numo_size = numo.size();
    int demo_size = demo.size();
    int min_val = min(numo_size, demo_size);
    for (int i = 1; i <= min_val; i++) {
        if (numo_size % i == 0) {
            if (demo_size % i == 0) {
                if (numo.substr(0, i) == demo.substr(0, i)) {
                    if (verify(numo, i) == 1) {
                        if (verify(demo, i) == 1) {
                            count++;
                        }
                    }
                }
            }
        }
    }
    return count;
}

int main() {
    string numo = "abababab";
    string demo = "abababababababab";
    cout << "Count the number of common divisors of the given strings are: " << common_divisor(numo, demo);
    return 0;
}

আউটপুট

Count the number of common divisors of the given strings are: 3