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