QUESTION

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.

ANSWER

#include<bits/stdc++.h>

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;

	else
		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];
scanf("%s",X);
  scanf("%s",Y);
int m = strlen(X);
int n = strlen(Y);

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

return 0;
}