सबसे लंबा सामान्य परिणाम

इस ट्यूटोरियल में, आप सीखेंगे कि सबसे लंबी सामान्य परिणाम कैसे पाए जाते हैं। साथ ही, आपको C, C ++, जावा और पायथन में सबसे लंबे समय तक सामान्य कार्य करने के उदाहरण मिलेंगे।

सबसे लंबी सामान्य परवर्तीता (LCS) को सबसे लंबी अनुवर्तीता के रूप में परिभाषित किया गया है जो सभी दिए गए अनुक्रमों के लिए सामान्य है, बशर्ते कि बाद के तत्वों को मूल अनुक्रमों के भीतर लगातार पदों पर कब्जा करने की आवश्यकता न हो।

यदि S1 और S2 दो दिए गए क्रम हैं, तो Z, S1 और S2 का सामान्य परिणाम है, यदि Z S1 और S2 दोनों का अनुवर्ती है। इसके अलावा, Z को S1 और S2 दोनों के सूचकांकों का सख्ती से बढ़ता क्रम होना चाहिए ।

कड़ाई से बढ़ते अनुक्रम में, मूल अनुक्रमों से चुने गए तत्वों के सूचकांक Z में आरोही क्रम में होने चाहिए।

अगर

 एस 1 = (बी, सी, डी, ए, ए, सी, डी)

फिर, (A, D, B)S1 की कोई अनुवर्तीता नहीं हो सकती है क्योंकि तत्वों का क्रम समान नहीं है (यानी अनुक्रम को सख्ती से नहीं बढ़ाया जा रहा है)।

आइए LCS को एक उदाहरण से समझते हैं।

अगर

 एस 1 = (बी, सी, डी, ए, ए, सी, डी) एस 2 = (ए, सी, डी, बी, ए, सी)

फिर, सामान्य अनुवर्ती हैं (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

इन नतीजों में, (C, D, A, C)सबसे लंबे समय तक चलने वाला सामान्य परिणाम है। हम गतिशील प्रोग्रामिंग का उपयोग करते हुए इस सबसे लंबे सामान्य परिणाम को खोजने जा रहे हैं।

आगे बढ़ने से पहले, यदि आप पहले से ही गतिशील प्रोग्रामिंग के बारे में नहीं जानते हैं, तो कृपया गतिशील प्रोग्रामिंग से गुजरें।

LCS खोजने के लिए डायनामिक प्रोग्रामिंग का उपयोग करना

आइए हम दो क्रम लेते हैं:

पहला क्रम

दूसरा क्रम

निम्न चरणों का पालन सबसे लंबे समय तक होने वाली सामान्य खोज के लिए किया जाता है।

आयाम की एक तालिका बनाएं n+1*m+1जहां n और m क्रमशः X और Y की लंबाई हैं। पहली पंक्ति और पहला कॉलम शून्य से भरे हुए हैं। प्रारंभिक तालिका
निम्न तर्क का उपयोग करके तालिका के प्रत्येक सेल को भरें।
यदि वर्तमान पंक्ति और वर्तमान स्तंभ से संबंधित वर्ण मेल कर रहे हैं, तो वर्तमान कोशिका को विकर्ण तत्व में जोड़कर भरें। विकर्ण कोशिका के लिए एक तीर इंगित करें।
वर्तमान सेल को भरने के लिए पिछले कॉलम और पिछले पंक्ति तत्व से अधिकतम मान लें। अधिकतम मान वाले सेल पर तीर को इंगित करें। यदि वे समान हैं, तो उनमें से किसी को इंगित करें। मान भरें
चरण 2 को तब तक दोहराया जाता है जब तक कि तालिका भर न जाए। सभी मान भरें
अंतिम पंक्ति और अंतिम कॉलम में मूल्य सबसे लंबे समय तक सामान्य बाद की लंबाई है। निचला दायां कोना LCS की लंबाई है
सबसे लंबे सामान्य परिणाम को खोजने के लिए, अंतिम तत्व से शुरू करें और तीर की दिशा का पालन करें। () प्रतीक के अनुरूप तत्व सबसे लंबे समय तक सामान्य रूप बनाते हैं। तीरों के हिसाब से रास्ता बनाएं

इस प्रकार, सबसे लंबी सामान्य बाद की सीडी है।

एलसीएस

एलसीएस समस्या का समाधान करते समय एक गतिशील प्रोग्रामिंग एल्गोरिदम पुनरावर्ती एल्गोरिदम से अधिक कुशल कैसे है?

डायनेमिक प्रोग्रामिंग की विधि फ़ंक्शन कॉल की संख्या को कम करती है। यह प्रत्येक फ़ंक्शन कॉल के परिणाम को संग्रहीत करता है ताकि इसे भविष्य की कॉल में अनावश्यक कॉल की आवश्यकता के बिना उपयोग किया जा सके।

उपरोक्त गतिशील एल्गोरिथ्म में, एक्स के तत्वों और वाई के तत्वों के बीच प्रत्येक तुलना से प्राप्त परिणाम एक तालिका में संग्रहीत किए जाते हैं ताकि उन्हें भविष्य की गणना में उपयोग किया जा सके।

तो, एक गतिशील दृष्टिकोण द्वारा लिया गया समय तालिका भरने का समय है (यानी ओ। (एमएन))। जबकि, पुनरावृत्ति एल्गोरिथ्म में 2 ^{अधिकतम (एम, एन)} की जटिलता है ।

सबसे लंबे समय तक सामान्य उपसर्ग एल्गोरिथम

 X और Y दो दिए गए क्रम हैं। एक तालिका LCS का आयाम शुरू करें। X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 LCS से प्रारंभ करें ( 1) (1) X (i) और Y (j) यदि X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) की तुलना LCS के लिए तीर करें (i) (j) एल्स LCS (i) (j) = अधिकतम (LCS (i-1) (j), LCS (i) (j-1)) अधिकतम तीर को इंगित करें (LCS (i-1) () j), LCS (i) (j-1))

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++

 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )

 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )

 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )