C++ में दो स्ट्रिंग्स में सामान्य उपअनुक्रम गिनना

हमें दो स्ट्रिंग्स दी गई हैं, मान लीजिए str1 और str2 जिनमें कैरेक्टर्स हैं और कार्य दोनों स्ट्रिंग्स में सामान्य उपअनुक्रमों की गणना करना है। नीचे दिए गए प्रोग्राम में हम डायनामिक प्रोग्रामिंग का उपयोग कर रहे हैं और उसके लिए हमें पता होना चाहिए कि डायनामिक प्रोग्रामिंग क्या है और किन समस्याओं में इसका उपयोग किया जा सकता है।

डायनामिक प्रोग्रामिंग दृष्टिकोण समस्या को छोटे और फिर छोटे संभावित सब-प्रॉब्लम्स में तोड़ने में विभाजन और विजय के समान है। लेकिन, विभाजन और विजय के विपरीत, ये सब-प्रॉब्लम्स स्वतंत्र रूप से हल नहीं होते हैं। बल्कि, इन छोटे सब-प्रॉब्लम्स के परिणामों को याद रखा जाता है और समान या ओवरलैपिंग सब-प्रॉब्लम्स के लिए उपयोग किया जाता है।

डायनामिक प्रोग्रामिंग का उपयोग वहां किया जाता है जहां हमारे पास ऐसी समस्याएं होती हैं जिन्हें समान सब-प्रॉब्लम्स में विभाजित किया जा सकता है, ताकि उनके परिणामों का पुन: उपयोग किया जा सके। ज्यादातर, इन एल्गोरिदम का उपयोग अनुकूलन के लिए किया जाता है। हाथ में सब-प्रॉब्लम को हल करने से पहले, डायनामिक एल्गोरिदम पहले हल किए गए सब-प्रॉब्लम्स के परिणामों की जांच करने का प्रयास करेंगे। सब-प्रॉब्लम्स के समाधानों को सर्वोत्तम समाधान प्राप्त करने के लिए संयोजित किया जाता है।

उदाहरण

इनपुट: string str1 = "abc", String str2 = "ab"

आउटपुट: count is 3

व्याख्या: दी गई स्ट्रिंग्स से बने सामान्य उपअनुक्रम हैं: {'a', 'b', 'ab'}।

इनपुट: string str1 = "ajblqcpdz", String str2 = "aefcnbtdi"

आउटपुट: count is 11

सामान्य उपअनुक्रम हैं: दी गई स्ट्रिंग्स से बने सामान्य उपअनुक्रम हैं: {"a", "b", "c", "d", "ab", "bd", "ad", "ac", "cd", "abd", "acd"}

उपयोग किया गया दृष्टिकोण:

• दो स्ट्रिंग्स इनपुट करें मान लीजिए str1 और str2
• length() फ़ंक्शन का उपयोग करके दी गई स्ट्रिंग की लंबाई की गणना करें और इसे str1 के लिए len1 और str2 के लिए len2 में स्टोर करें
• डायनामिक प्रोग्रामिंग लागू करने के लिए एक 2-D ऐरे बनाएं मान लीजिए arr[len1+1][len2+1]
• i के लिए 0 से लूप शुरू करें जब तक i <= len1:
  • लूप के अंदर, j के लिए 0 से लूप शुरू करें जब तक j <= len2:
    • लूप के अंदर, जांचें यदि str1[i-1] == str2[j-1] तो arr[i][j] = 1 + arr[i][j-1] + arr[i-1][j] सेट करें
    • अन्यथा, arr[i][j] = arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1] सेट करें
• arr[len1][len2] वापस करें
• परिणाम प्रिंट करें।

उदाहरण (C++ कोड)

#include <iostream> 
using namespace std; 
// स्ट्रिंग में उपअनुक्रमों की संख्या गिनने के लिए 
int countsequences(string str, string str2){ 
    int n1 = str.length(); 
    int n2 = str2.length(); 
    int dp[n1+1][n2+1]; 
    for (int i = 0; i <= n1; i++){ 
        for (int j = 0; j <= n2; j++){ 
            dp[i][j] = 0; 
        } 
    } 
    // str के प्रत्येक कैरेक्टर के लिए 
    for (int i = 1; i <= n1; i++){ 
        // str2 में प्रत्येक कैरेक्टर के लिए 
        for (int j = 1; j <= n2; j++){ 
            // यदि दोनों स्ट्रिंग्स में कैरेक्टर समान हैं 
            if (str[i - 1] == str2[j - 1]){ 
                dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j]; 
            } 
            else{ 
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]; 
            } 
        } 
    } 
    return dp[n1][n2]; 
} 
int main(){ 
    string str = "abcdejkil"; 
    string str2 = "bcdfkaoenlp"; 
    cout << "count is: " << countsequences(str, str2) << endl; 
    return 0; 
}

आउटपुट

count is: 51