सी ++ में सबसे छोटा सामान्य सुपरसीक्वेंस

मान लीजिए कि हमारे पास दो स्ट्रिंग्स str1 और str2 हैं, हमें सबसे छोटी स्ट्रिंग ढूंढनी है जिसमें str1 और str2 दोनों बाद के रूप में हों। एक से अधिक परिणाम हो सकते हैं, इसलिए हम उनमें से केवल एक को ही लौटाएंगे।

जैसा कि आप जानते हैं कि एक स्ट्रिंग एस को स्ट्रिंग टी के बाद कहा जाता है यदि टी से कुछ वर्णों को हटा दिया जाता है (संभवतः 0, और अक्षर टी से कहीं भी चुने जाते हैं) परिणाम स्ट्रिंग एस में होता है।

इसलिए, यदि इनपुट "acab", "bac" जैसा है, तो आउटपुट "bacab" होगा, ऐसा इसलिए है क्योंकि दो दिए गए तार इसके बाद के हैं।

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

• getLCS() फ़ंक्शन को परिभाषित करें, इसमें s1, s2,

  लगेगा

• रिट:=खाली स्ट्रिंग

• n :=s1 का आकार, m :=s2 का आकार

• एक 2D सरणी dp आकार (n + 1) x (m + 1) परिभाषित करें

• मैं :=n, j :=m

• s1 :=s1 से पहले रिक्त स्ट्रिंग को संयोजित करें

• s2 :=s2 से पहले रिक्त स्ट्रिंग को संयोजित करें

• इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ j :=1 के लिए, जब j <=m, अपडेट करें (j को 1 से बढ़ाएँ), करें -

    • अगर s1[i] s2[j] के समान है, तो -

      • dp[i, j] :=1 + dp[i-1, j-1]

    • अन्यथा

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

• जबकि (i गैर-शून्य है और j गैर-शून्य है), करें -

  • अगर dp[i, j] dp[i - 1, j] के समान है, तो -

    • (i 1 से घटाएं)

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • अगर dp[i, j] dp[i, j-1] के समान है, तो -

    • (j को 1 से घटाएं)

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • रिट :=रिट + s1[i]

  • (i 1 से घटाएं)

  • (j को 1 से घटाएं)

• सरणी को उलट दें रिट

• वापसी रिट

• मुख्य विधि से निम्न कार्य करें -

• s3 :=getLCS(str1, str2)

• ret :=खाली स्ट्रिंग, i :=0, j :=0, k :=0

• जबकि k

  • अगर i

    • रिट :=रिट + str1[i]

    • (मैं 1 से बढ़ाइए)

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • अगर j

    • रिट :=रिट + str2[j]

    • (जम्मू को 1 से बढ़ाएं)

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • रिट :=रिट + s3[k]

  • (i, j, k को 1 से बढ़ाएं)

• जबकि मैं

  • रिट :=रिट + str1[i]

  • (मैं 1 से बढ़ाइए)

• जबकि j

  • रिट :=रिट + str2[j]

  • (जम्मू को 1 से बढ़ाएं)

• वापसी रिट

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string shortestCommonSupersequence(string str1, string str2){
      string s3 = getLCS(str1, str2);
      string ret = "";
      int i = 0;
      int j = 0;
      int k = 0;
      while (k < s3.size()) {
         if (i < str1.size() && str1[i] != s3[k]) {
            ret += str1[i];
            i++;
            continue;
         }
         if (j < str2.size() && str2[j] != s3[k]) {
            ret += str2[j];
            j++;
            continue;
         }
         ret += s3[k];
         k++;
         i++;
         j++;
      }
      while (i < str1.size()) {
         ret += str1[i];
         i++;
      }
      while (j < str2.size()) {
         ret += str2[j];
         j++;
      }
      return ret;
   }
   string getLCS(string s1, string s2){
      string ret = "";
      int n = s1.size();
      int m = s2.size();
      vector<vector<int> > dp(n + 1, vector<int>(m + 1));
      int i = n;
      int j = m;
      s1 = " " + s1;
      s2 = " " + s2;
      for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= m; j++) {
            if (s1[i] == s2[j]) {
               dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
               dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
         }
      }
      while (i && j) {
         if (dp[i][j] == dp[i - 1][j]) {
            i--;
            continue;
         }
         if (dp[i][j] == dp[i][j - 1]) {
            j--;
            continue;
         }
         ret += s1[i];
         i--;
         j--;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestCommonSupersequence("acab", "bac"));
}

इनपुट

"acab", "bac"

आउटपुट

bacab