একটি সাবসিকোয়েন্স হলো এলিমেন্টের একটি সেট যাদের অর্ডার মূল সিকোয়েন্সের মতোই থাকে। "stuv" সিকোয়েন্সের জন্য, সাবসিকোয়েন্সগুলো হলো "stu", "tuv", "suv", ইত্যাদি।
লেন্থ n-এর একটি স্ট্রিং-এর জন্য, স্ট্রিং থেকে সাবসিকোয়েন্স তৈরি করার 2ⁿ পথ থাকতে পারে।
উদাহরণ
"ABCDGH" এবং "AEDFHR" স্ট্রিং দুটির লংগেস্ট কমন সাবসিকোয়েন্সের লেন্থ ৩।
#include <iostream> #include <string.h> using namespace std; int max(int a, int b); int lcs(char* X, char* Y, int m, int n){ if (m == 0 || n == 0) return 0; if (X[m - 1] == Y[n - 1]) return 1 + lcs(X, Y, m - 1, n - 1); else return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n)); } int max(int a, int b){ return (a > b) ? a : b; } int main(){ char X[] = "AGGTAB"; char Y[] = "GXTXAYB"; int m = strlen(X); int n = strlen(Y); printf("Length of LCS is %d\n", lcs(X, Y, m, n)); return 0; }
আউটপুট
Length of LCS is 4
