এই সমস্যায়, আমাদের দুটি স্ট্রিং str1 এবং str2 দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যাতে সকল দীর্ঘতম সাধারণ অনুসৃতি অভিধানিক ক্রমে প্রিন্ট করা যায়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: str1 ="gfare" , str2 ="rfare"
আউটপুট: ভাড়া
সমাধান পদ্ধতি
এই সমস্যায়, আমরা সমস্ত সম্ভাব্য দীর্ঘতম সাধারণ অনুবর্তনগুলি খুঁজে পাব এবং ডায়নামিক প্রোগ্রামিং ব্যবহার করে একটি 2D ম্যাট্রিক্সে সেগুলি সংরক্ষণ করব। এর পরে, আমরা সর্টেড আউটপুট প্রিন্ট করব LCS এ a থেকে z পর্যন্ত অক্ষর অনুসন্ধান করে।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
