আমাদের একটি স্ট্রিং str এবং দৈর্ঘ্য ৩-এর একটি সাবস্ট্রিং sub_str দেওয়া আছে। লক্ষ্য হলো str-এ sub_str কতবার সাবসিকোয়েন্স (subsequence) হিসেবে পাওয়া যায়। উদাহরণস্বরূপ, "act" ত্রিবার পাওয়া যায় "cataract"-এ (cataract, cataract, cataract)।
উদাহরণ দিয়ে বুঝি
ইনপুট − str="settlement", sub_str="set"
আউটপুট − দৈর্ঘ্য ৩-এর সাবসিকোয়েন্স কাউন্ট: ৫
ব্যাখ্যা − সাবসিকোয়েন্স গুলো:
1. set tlement, 2. se t t lement, 3. se ttlemen t, 4. s ettl e men t, 5. settlem e n t
ইনপুট − str="knowledge", sub_str="now"
আউটপুট − দৈর্ঘ্য ৩-এর সাবসিকোয়েন্স কাউন্ট: ১
ব্যাখ্যা − সাবসিকোয়েন্স: know ledge
প্রোগ্রামে ব্যবহৃত পদ্ধতি
for লুপ দিয়ে স্ট্রিং ট্রাভার্স করব। যদি str[i]==sub_str[0] হয়, তবে পরবর্তী ক্যারেক্টার sub_str[1] খুঁজব j=i+1 থেকে। মিল পাওয়া গেলে শেষ ক্যারেক্টার sub_str[2] খুঁজব k=j+1 থেকে। দুটি মিল পাওয়া গেলে কাউন্ট বাড়াব।
- স্ট্রিং
strএবং সাবস্ট্রিংsub_strনিন। subset_occurrence(string str, int length, string sub_str)ফাংশন স্ট্রিং গুলো নিয়েsub_strমэтচ সাবসিকোয়েন্স কাউন্ট রিটার্ন করে।i=0থেকেlengthপর্যন্ত লুপে:str[i]==sub_str[0]হলে:j=i+1থেকেlengthপর্যন্ত লুপেsub_str[1]খুঁজুন।- মিল পাওয়া গেলে:
k=j+1থেকেlengthপর্যন্ত লুপেsub_str[2]খুঁজুন। - মিল পাওয়া গেলে
count++।
countরিটার্ন করুন।
উদাহরণ
#include <iostream>
using namespace std;
int subset_occurrence(string str, int length, string sub_str) {
int count = 0;
for (int i = 0; i < length; i++) {
if (str[i] == sub_str[0]) {
for (int j = i + 1; j < length; j++) {
if (str[j] == sub_str[1]) {
for (int k = j + 1; k < length; k++) {
if (str[k] == sub_str[2]) {
count++;
}
}
}
}
}
}
return count;
}
int main() {
string str = "TUTpoinTUTpoinTUT";
int length = str.length();
string sub_str = "TUT";
cout << "Count of subsequence of length three in a given string are: " << subset_occurrence(str, length, sub_str);
return 0;
}
আউটপুট
Count of subsequence of length three in a given string are: 19
