एक सबसीक्वेंस तत्वों के समूह का वही क्रम वाला अनुक्रम है। अनुक्रम "stuv" के लिए, सबसीक्वेंस हैं "stu", "tuv", "suv", आदि।
लंबाई n के एक स्ट्रिंग के लिए, उस स्ट्रिंग से सबसीक्वेंस बनाने के 2^n तरीके हो सकते हैं।
उदाहरण
स्ट्रिंग्स "ABCDGH" और "AEDFHR" के लिए सबसे लंबी सामान्य सबसीक्वेंस की लंबाई 3 है।
#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
