একটি পরবর্তী উপাদানের সেটের একই ক্রম সহ একটি অনুক্রম। ক্রম "stuv" এর জন্য, পরবর্তী গুলি হল "stu", "tuv", "suv",.... ইত্যাদি।
n দৈর্ঘ্যের একটি স্ট্রিংয়ের জন্য, স্ট্রিং থেকে পরবর্তী সূচনা তৈরি করার 2n উপায় থাকতে পারে।
উদাহরণ
"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
