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

C++ में सबसे लंबे सामान्य उपअनुक्रम की लंबाई खोजने का प्रोग्राम


मान लीजिए हमारे पास दो स्ट्रिंग्स text1 और text2 हैं, हमें उनके सबसे लंबे सामान्य उपअनुक्रम (Longest Common Subsequence - LCS) की लंबाई ज्ञात करनी है। एक उपअनुक्रम वह स्ट्रिंग है जो मूल स्ट्रिंग से कुछ वर्णों को हटाकर (बिना क्रम बदले) बनती है। उदाहरण के लिए, "abe" "abcde" का उपअनुक्रम है लेकिन "adc" नहीं।

यदि इनपुट "abcde" और "ace" है, तो परिणाम 3 होगा (उपअनुक्रम "ace")।

समाधान दृष्टिकोण

हम डायनामिक प्रोग्रामिंग का उपयोग करते हैं:

  • n := text1 का आकार, m := text2 का आकार।
  • यदि n या m शून्य है, तो 0 वापस करें।
  • दोनों स्ट्रिंग्स के आगे एक खाली स्थान जोड़ें (1-आधारित इंडेक्सिंग के लिए)।
  • आकार (n+1) x (m+1) का एक 2D DP सरणी बनाएं।
  • i = 1 से n तक और j = 1 से m तक पुनरावृति करें:
    • dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    • यदि s[i] == x[j], तो dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1])
  • dp[n][m] वापस करें।

C++ कार्यान्वयन

#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;
        vector> dp(n + 1, vector(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];
    }
};

int main() {
    Solution ob;
    cout << ob.longestCommonSubsequence("abcde", "ace");
    return 0;
}

इनपुट

"abcde" "ace"

आउटपुट

3
  1. - पायथन में सबसे लंबी बढ़ती हुई उप-अनुक्रम की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास संख्याओं की एक सूची है। हमें सबसे लंबी बढ़ती हुई उप-अनुक्रम (Longest Increasing Subsequence) की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट [6, 1, 7, 2, 8, 3, 4, 5] है, तो आउटपुट 5 होगा, क्योंकि सबसे लंबी बढ़ती हुई उप-अनुक्रम [2, 3, 4, 5, 6] है। इसे हल करने के लिए हम निम्न चरणों का

  1. - पायथन में सबसे लंबी एनाग्राम उप-अनुक्रम की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास दो लोअरकेस स्ट्रिंग्स S और T हैं, हमें सबसे लंबी एनाग्राम उप-अनुक्रम की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट S = helloworld, T = hellorld है, तो आउटपुट 8 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: c := एक नया मैप, d := एक नया मैप। i को 0 से len(a) - 1 तक लूप म

  1. - पायथन में सबसे लंबे संतुलित उप-अनुक्रम की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें ब्रैकेट्स ( और ) हैं, हमें संतुलित ब्रैकेट्स के सबसे लंबे उप-अनुक्रम की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट s = ())(()( है, तो आउटपुट 4 होगा, क्योंकि हम ()() जैसा उप-अनुक्रम ले सकते हैं। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: res := 0, n