Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में लॉन्गेस्ट कॉमन सबसीक्वेंस


मान लीजिए हमारे पास दो स्ट्रिंग्स text1 और text2 हैं, हमें उनकी सबसे लंबी सामान्य सबसीक्वेंस की लंबाई लौटानी है। एक स्ट्रिंग की सबसीक्वेंस मूल स्ट्रिंग से कुछ कैरेक्टर्स को हटाकर बिना शेष कैरेक्टर्स के सापेक्ष क्रम को बदले उत्पन्न एक नई स्ट्रिंग है। (उदाहरण के लिए "abe" "abcde" की सबसीक्वेंस है लेकिन "adc" नहीं)। दो स्ट्रिंग्स की सामान्य सबसीक्वेंस वह सबसीक्वेंस है जो दोनों स्ट्रिंग्स के लिए सामान्य है। इसलिए यदि कोई सामान्य सबसीक्वेंस नहीं है, तो 0 लौटाएं। अगर इनपुट "abcde" और "ace" है, तो परिणाम 3 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

  • n := s का आकार, m := x का आकार

  • यदि n 0 है, या m 0 है, तो 0 लौटाएं

  • s := खाली स्ट्रिंग, s के साथ संयोजित

  • x := खाली स्ट्रिंग, x के साथ संयोजित

  • ret := 0

  • क्रम (n + 1) x (m + 1) का एक मैट्रिक्स dp परिभाषित करें

  • i को 1 से n तक रेंज में लिए:

    • j को 1 से m तक रेंज में लिए:

      • dp[i, j] := dp[i, j - 1] और dp[i - 1, j] का अधिकतम

      • यदि s[i] = x[j], तो

        • dp[i, j] := dp[i, j] का अधिकतम, 1 + dp[i - 1, j - 1]

  • dp[n, m] लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int longestCommonSubsequence(string s, string x) {       int n = s.size();       int m = x.size();       if(!n || !m) return 0;       s = " " + s;       x = " " + x;       int ret = 0;       vector < vector <int> > dp(n + 1, vector <int>(m + 1));       for(int i = 1; i <= n; i++){          for(int j = 1; j <= m ; j++){             dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);             if(s[i] == x[j]) {                dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);             }          }       }       return dp[n][m];    } }; main(){    Solution ob;    cout << (ob.longestCommonSubsequence("abcde", "ace")); }

इनपुट

"abcde" "ace"

आउटपुट

3

  1. - C++ में Number of Longest Increasing Subsequence

    मान लीजिए हमारे पास पूर्णांकों की एक अक्रमबद्ध सरणी है। हमें सबसे लंबी बढ़ती उपअनुक्रम (longest increasing subsequence) की संख्या ढूंढनी है, इसलिए यदि इनपुट [1, 3, 5, 4, 7] जैसा है, तो आउटपुट 2 होगा, क्योंकि बढ़ते उपअनुक्रम [1,3,5,7] और [1, 3, 4, 7] हैं।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे

  1. - C++ प्रोग्राम: लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS)

    एक सबसीक्वेंस तत्वों के समूह का वही क्रम वाला अनुक्रम है। अनुक्रम stuv के लिए, सबसीक्वेंस हैं stu, tuv, suv, आदि। लंबाई n के एक स्ट्रिंग के लिए, उस स्ट्रिंग से सबसीक्वेंस बनाने के 2^n तरीके हो सकते हैं। उदाहरण स्ट्रिंग्स ABCDGH और AEDFHR के लिए सबसे लंबी सामान्य सबसीक्वेंस की लंबाई 3 है। #include &l

  1. - C++ प्रोग्राम: सीक्वेंस के सेट में सभी सीक्वेंस के लिए कॉमन सबसे लंबी सबसीक्वेंस खोजना

    यहां हम एक C++ प्रोग्राम पर चर्चा करेंगे जो एक सेट ऑफ सीक्वेंस में सभी सीक्वेंस के लिए कॉमन सबसे लंबी सबसीक्वेंस खोजता है। एल्गोरिदम Begin स्ट्रिंग्स की ऐरे को इनपुट के रूप में लें। function matchedPrefixtill(): स्ट्रिंग s1 और s2 के बीच मैच्ड प्रीफिक्स खोजें: n1 = स्ट्रिंग s1 की लं