মান লেইয়া দুটি স্ট্রিং X এবং Y, আমাদের X-এর সবচেয়ে বড় সাবসিকোয়েন্স (subsequence) খুঁজে বের করতে হবে যা Y-তে সাবস্ট্রিং (substring) হিসেবে আছে। উদাহরণস্বরূপ, X = "ABCD" এবং Y = "BACDBDCD" হলে আউটপুট হবে ৩। কারণ "ACD" হলো X-এর সবচেয়ে বড় সাবসিকোয়েন্স যা Y-তে সাবস্ট্রিং।
এটি সমাধানের জন্য ডাইনামিক প্রোগ্রামিং (DP) অ্যাপ্রোচ ব্যবহার করব। যদি X-এর দৈর্ঘ্য n এবং Y-এর দৈর্ঘ্য m হয়, তবে (m+1)x(n+1) আকারের DP অ্যারে তৈরি করব। DP[i, j]-এর মান হবে X[0...j]-এর সর্বোচ্চ দৈর্ঘ্যের সাবসিকোয়েন্স যা Y[0...i]-এ সাবস্ট্রিং। প্রতিটি DP সেলের জন্য নিচের নিয়ম মেনে চলবে:
- i = 1 থেকে m পর্যন্ত:
- j = 1 থেকে n পর্যন্ত
- যদি X[i - 1] == Y[j - 1] হয়, তবে DP[i, j] := 1 + DP[i - 1, j - 1]
- অন্যথায় DP[i, j] := DP[i, j - 1]
- j = 1 থেকে n পর্যন্ত
অবশেষে X-এর সাবসিকোয়েন্স যা Y-তে সাবস্ট্রিং, তার দৈর্ঘ্য হবে max(DP[i, n]), যেখানে 1 <= i <= m।
উদাহরণ
#include<iostream> #define MAX 100 using namespace std; int maxSubLength(string x, string y) { int table[MAX][MAX]; int n = x.length(); int m = y.length(); for (int i = 0; i <= m; i++) for (int j = 0; j <= n; j++) table[i][j] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (x[j - 1] == y[i - 1]) table[i][j] = 1 + table[i - 1][j - 1]; else table[i][j] = table[i][j - 1]; } } int ans = 0; for (int i = 1; i <= m; i++) ans = max(ans, table[i][n]); return ans; } int main() { string x = "ABCD"; string y = "BACDBDCD"; cout << "Length of Maximum subsequence substring is: " << maxSubLength(x, y); }আউটপুট
Length of Maximum subsequence substring is: 3
