Naive-Recursive: Longest Common Subsequence


LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. \n\nA subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. \n\nFor example, \”abc\”, \”abg\”,\”bdf\”, \”aeg\”, \”acefg\”, .. etc are subsequences of \”abcdefg\”. \n\nSo a string of length n has 2^n different possible subsequences.



int max(int a, int b);

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
int L[m+1][n+1];
int i, j;

/* Following steps build L[m+1][n+1] in bottom up fashion. Note 
	that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (i=0; i<=m; i++)
	for (j=0; j<=n; j++)
	if (i == 0 || j == 0)
		L[i][j] = 0;

	else if (X[i-1] == Y[j-1])
		L[i][j] = L[i-1][j-1] + 1;

		L[i][j] = max(L[i-1][j], L[i][j-1]);
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];

/* Utility function to get max of 2 integers */
int max(int a, int b)
	return (a > b)? a : b;

/* Driver program to test above function */
int main()
//char X[] = "ABCDGH";
//char Y[] = "AEDFHR";
  char X[10],Y[10];
int m = strlen(X);
int n = strlen(Y);

printf("Length of LCS is %d", lcs( X, Y, m, n ) );

return 0;
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro