C++-এ শর্টেস্ট কমন সুপারসিকোয়েন্স (Shortest Common Supersequence) বের করা

দুটি স্ট্রিং str1 এবং str2 দেওয়া আছে। এমন সবচোটে স্ট্রিং বের করতে হবে যেটিতে str1 এবং str2 দুটোই সাবসিকোয়েন্স হিসেবে থাকে। একাধিক সমাধান থাকলে যেকোনো একটি রিটার্ন করুন।

উদাহরণ

ইনপুট: "acab", "bac" → আউটপুট: "bacab"

ব্যাখ্যা: দুটি দেওয়া স্ট্রিং "bacab"-এর সাবসিকোয়েন্স।

সমাধানের ধাপসমূহ

1. প্রথমে LCS (Longest Common Subsequence) বের করুন।
2. তারপর LCS-এর ক্যারেক্টারগুলো মার্জ করে SCS বানান।
3. DP টেবিল বানাতে dp[i][j] = str1[0..i-1] এবং str2[0..j-1]-এর LCS দৈর্ঘ্য।
4. টেবিল থেকে LCS স্ট্রিং রিকভার করুন।
5. LCS ব্যবহার করে SCS কনস্ট্রাক্ট করুন।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        string lcs = getLCS(str1, str2);
        string ret = "";
        int i = 0, j = 0, k = 0;
        
        while (k < lcs.size()) {
            if (i < str1.size() && str1[i] != lcs[k]) {
                ret += str1[i++];
                continue;
            }
            if (j < str2.size() && str2[j] != lcs[k]) {
                ret += str2[j++];
                continue;
            }
            ret += lcs[k++];
            i++; j++;
        }
        while (i < str1.size()) ret += str1[i++];
        while (j < str2.size()) ret += str2[j++];
        return ret;
    }
    
    string getLCS(string s1, string s2) {
        string ret = "";
        int n = s1.size(), m = s2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        
        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]);
            }
        }
        
        int i = n, j = m;
        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;
    }
};

int main() {
    Solution ob;
    cout << (ob.shortestCommonSupersequence("acab", "bac"));
}

ইনপুট

"acab", "bac"

আউটপুট

bacab