इस समस्या में, हमें दो स्ट्रिंग str1 और str2 दिए गए हैं। हमारा काम एक प्रोग्राम बनाना है ताकि शब्दकोश के क्रम में सभी सबसे लंबे सामान्य अनुक्रमों को प्रिंट किया जा सके।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: str1 ="gfare", str2 ="rfare"
आउटपुट: किराया
समाधान दृष्टिकोण
इस समस्या में, हम सभी संभव सबसे लंबे समय तक सामान्य अनुक्रम पाएंगे और उन्हें गतिशील प्रोग्रामिंग का उपयोग करके 2 डी मैट्रिक्स में संग्रहीत करेंगे। इसके बाद, हम सॉर्ट किए गए आउटपुट को प्रिंट करेंगे 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