सी ++ में दो स्ट्रिंग्स में सामान्य बाद की गणना करें

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

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

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

तो हम कह सकते हैं कि -

Input − string str1 = “abc”
      String str2 = “ab”
Output − count is 3

स्पष्टीकरण - दिए गए स्ट्रिंग्स से बनने वाले सामान्य अनुवर्ती हैं:{'a', 'b' , 'ab'}।

Input − string str1 = “ajblqcpdz”
      String str2 = “aefcnbtdi”
Output − count is 11

आम परिणाम हैं - दिए गए स्ट्रिंग्स से बनने वाले सामान्य परिणाम हैं:{ "a", "b", "c", "d", "ab", "bd", "ad", "ac", "cd", "abd" , "एसीडी" }

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

• दो स्ट्रिंग इनपुट करें मान लें कि str1 और str2।

• दिए गए स्ट्रिंग की लंबाई की गणना लंबाई () फ़ंक्शन का उपयोग करके करें जो एक स्ट्रिंग में वर्णों की संख्या के अनुसार एक पूर्णांक मान लौटाएगा और इसे str1 के लिए len1 में और str2 के लिए len2 में संग्रहीत करेगा।

• गतिशील प्रोग्रामिंग को लागू करने के लिए 2-डी सरणी बनाएं मान लें कि arr[len1+1][len2+1]

• i से 0 के लिए लूप प्रारंभ करें जब तक कि i len1 से कम न हो

• लूप के अंदर, j से 0 के लिए एक और लूप शुरू करें जब तक कि j len2 से कम न हो

• लूप के अंदर, IF 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]

  सेट करें

• वापसी गिरफ्तारी[len1][len2]

• परिणाम प्रिंट करें।

उदाहरण

#include <iostream>
using namespace std;
// To count the number of subsequences in the string
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;
      }
   }
   // for each character of str
   for (int i = 1; i <= n1; i++){
      // for each character in str2
      for (int j = 1; j <= n2; j++){
         // if character are same in both
         // the string
         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