সর্বোচ্চ সাধারণ সাবসিকোয়েন্স (LCS) দৈর্ঘ্য (C++)

এই সমস্যায় দুটি স্ট্রিং text1 এবং text2 দেওয়া আছে। তাদের সর্বোচ্চ সাধারণ সাবসিকোয়েন্স (Longest Common Subsequence) এর দৈর্ঘ্য বের করতে হবে।

সাবসিকোয়েন্স কী?

মূল স্ট্রিং থেকে কিছু ক্যারেক্টার ডিলিট করে (অবস্থান বদলে না) বने নতুন স্ট্রিং। যেমন "abe" হলো "abcde"-র সাবসিকোয়েন্স, কিন্তু "adc" নয়।

উদাহরণ

ইনপুট: "abcde", "ace"

আউটপুট: 3 (LCS = "ace")

ডাইনামিক প্রোগ্রামিং সমাধান

dp[i][j] = text1[0..i-1] এবং text2[0..j-1]-র LCS দৈর্ঘ্য।

dp[i][j] = max(dp[i-1][j], dp[i][j-1])
যদি text1[i-1] == text2[j-1] হয়, dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1])

C++ প্রোগ্রাম

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

class Solution {
public:
    int longestCommonSubsequence(string s, string x) {
        int n = s.size(), m = x.size();
        if (!n || !m) return 0;
        s = " " + s; // 1-ইন্ডেক্সড
        x = " " + x;

        vector<vector<int>> dp(n + 1, vector<int>(m + 1));

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                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;
}