এই সমস্যায় আমাদের দুটি স্ট্রিং str1 এবং str2 দেওয়া আছে। আমাদের কাজ সবচেয়ে বড় কমন সাবসিকোয়েন্সগুলো লেক্সিকোগ্রাফিক্যাল অর্ডারে প্রিন্ট করা।
উদাহরণ:
ইনপুট: str1 = “gfare” , str2 = “rfare”
আউটপুট: fare
সমাধানের পদ্ধতি
এই সমস্যায় আমরা সব সম্ভাব্য লংগেস্ট কমন সাবসিকোয়েন্স খুঁজে বের করব এবং সেগুলো একটি ২D ম্যাট্রিক্সে ডাইনামিক প্রোগ্রামিং ব্যবহার করে স্টোর করব। এরপর সর্টেড আউটপুট প্রিন্ট করব a থেকে z পর্যন্ত ক্যারেক্টার সার্চ করে LCS-এ।
আমাদের সমাধান দেখানোর প্রোগ্রাম
উদাহরণ
#include<iostream> #include<cstring> #define MAX 100 using namespace std; int LCSLength = 0; int DP[MAX][MAX]; int calcLCSLenght(string str1, string str2, int l1, int l2, int i, int j) { int &lcsLen = DP[i][j]; if (i==l1 || j==l2) return lcsLen = 0; if (lcsLen != -1) return lcsLen; lcsLen = 0; if (str1[i] == str2[j]) lcsLen = 1 + calcLCSLenght(str1, str2, l1, l2, i+1, j+1); else lcsLen = max(calcLCSLenght(str1, str2, l1, l2, i+1, j), calcLCSLenght(str1, str2, l1, l2, i, j+1)); return lcsLen; } void printAllLCS(string str1, string str2, int l1, int l2, char data[], int index1, int index2, int currentLCSlength) { if (currentLCSlength == LCSLength) { data[currentLCSlength] = '\0'; puts(data); return; } if (index1==l1 || index2==l2) return; for (char ch='a'; ch<='z'; ch++) { bool done = false; for (int i=index1; i<l1; i++) { if (ch==str1[i]) { for (int j=index2; j<l2; j++) { if (ch==str2[j] && calcLCSLenght(str1, str2, l1, l2, i, j) == LCSLength-currentLCSlength) { data[currentLCSlength] = ch; printAllLCS(str1, str2, l1, l2, data, i+1, j+1, currentLCSlength+1); done = true; break; } } } if (done) break; } } } int main() { string str1 = "xysxysx", str2 = "xsyxsyx"; int l1 = str1.length(), l2 = str2.length(); memset(DP, -1, sizeof(DP)); LCSLength = calcLCSLenght(str1, str2, l1, l2, 0, 0); char data[MAX]; cout<<"All longest common sub-sequences in lexicographical order are\n"; printAllLCS(str1, str2, l1, l2, data, 0, 0, 0); return 0; }আউটপুট
All longest common sub-sequences in lexicographical order are xsxsx xsxyx xsysx xysyx xyxsx xyxyx
