C++-এ দীর্ঘতম সাধারণ সাবসিকোয়েন্স (LCS) এর দৈর্ঘ্য বের করার প্রোগ্রাম

সমস্যা বিবরণ

দুটি স্ট্রিং text1 এবং text2 দেওয়া থাকলে, তাদের দীর্ঘতম সাধারণ সাবসিকোয়েন্স (Longest Common Subsequence - LCS) এর দৈর্ঘ্য খুঁজে বের করতে হবে। সাবসিকোয়েন্স বলতে একটি স্ট্রিং-এর কয়েকটি ক্যারেক্টার ডিলিট করে (বাকি ক্যারেক্টারগুলোর অর্ডার বদলാതেই) নতুন স্ট্রিং তৈরি করা বোঝায়।

উদাহরণ: "abcde" এবং "ace" এর LCS হল "ace", দৈর্ঘ্য 3।

সমাধানের পদ্ধতি

এটি একটি ক্লাসিক ডাইনামিক প্রোগ্রামিং সমস্যা। নিচে ধাপগুলো দেওয়া হলো:

1. দুটি স্ট্রিং-এর দৈর্ঘ্য নিন: n = s.size(), m = x.size()।
2. যদি কোনো একটি স্ট্রিং খালি হয়, তবে 0 রিটার্ন করুন।
3. স্ট্রিংগুলোতে শুরুতে একটি স্পেস যোগ করুন (1-বেসড ইন্ডেক্সিংয়ের জন্য)।
4. একটি ২D DP টেবিল dp[n+1][m+1] তৈরি করুন।
5. নেস্টেড লুপ চালান: i = 1 থেকে n, j = 1 থেকে m।
6. প্রতি সেলের জন্য:
   • dp[i][j] = max(dp[i][j-1], dp[i-1][j])
   • যদি s[i] == x[j] হয়, তবে dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1])
7. শেষে dp[n][m] রিটার্ন করুন।

C++ কোড উদাহরণ

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

class Solution {
public:
    int longestCommonSubsequence(string s, string x) {
        int n = s.size();
        int m = x.size();
        if (!n || !m) return 0;
        
        s = " " + s;
        x = " " + x;
        
        vector> dp(n + 1, vector(m + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                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;
}

ইনপুট ও আউটপুট

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

আউটপুট: 3

মন্তব্য

এই এলগরিদমটি O(n×m) সময় ও স্থান জটিলতায় চলে। স্পেস অপ্টিমাইজেশন করে O(min(n,m)) স্থানে আনা সম্ভব।