আমাদের দুটি স্ট্রিং str1 এবং str2 দেওয়া আছে। কাজ হল দুটি স্ট্রিং-এ কমন সাবসিকোয়েন্স (Common Subsequence) - অর্থাৎ যেসব সিকোয়েন্স দুটি স্ট্রিং-এই কানোনিক্যাল অর্ডারে পাওয়া যায় - তাদের মোট সংখ্যা গণনা করা। এখানে ডাইনামিক প্রোগ্রামিং (Dynamic Programming) ব্যবহার করা হয়েছে।
ডাইনামিক প্রোগ্রামিং সমস্যাকে ছোট ছোট সাব-প্রობলেমে ভাগ করে সমাধান করে এবং ওভারল্যাপিং সাব-প্রোবলেমের ফলাফল মেমোরাইজ (memoize) করে রি-ইউজ করে। এটি অপ্টিমাইজেশন সমস্যায় ব্যবহৃত হয়।
উদাহরণ:
ইনপুট: str1 = "abc", str2 = "ab" → আউটপুট: count is 3 ({'a', 'b', 'ab'})
ইনপুট: str1 = "ajblqcpdz", str2 = "aefcnbtdi" → আউটপুট: count is 11
অ্যালগরিদম
দুটি স্ট্রিং ইনপুট নিন, দৈর্ঘ্য len1, len2 বের করুন
2D DP অ্যারে dp[len1+1][len2+1] তৈরি করুন, ০ দিয়ে ইনিশিয়ালাইজ করুন
i = 1 থেকে len1, j = 1 থেকে len2 পর্যন্ত লুপ:
যদি str1[i-1] == str2[j-1]: dp[i][j] = 1 + dp[i][j-1] + dp[i-1][j]
অন্যথায়: dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
dp[len1][len2] রিটার্ন করুন
প্রোগ্রাম
#include <iostream>
using namespace std;
int countsequences(string str, string str2) {
int n1 = str.length();
int n2 = str2.length();
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++)
for (int j = 0; j <= n2; j++)
dp[i][j] = 0;
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (str[i - 1] == str2[j - 1])
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
}
}
return dp[n1][n2];
}
int main() {
string str = "abcdejkil";
string str2 = "bcdfkaoenlp";
cout << "count is: " << countsequences(str, str2) << endl;
return 0;
}
আউটপুট
count is: 51
