## Answers

A example given in sample output with answer ATGGC is wrong

There can be many lcs for a pair of strings i have only printed one

#include <bits/stdc++.h>

using namespace std;

void LongestCommonSubsequence(string X,string Y)

{

int m=X.length(),n=Y.length();

int dp[m+1][n+1];

//initialise dp with 0

memset(dp,0,sizeof(dp));

for(int i=0;i<=m;i++)

{

for(int j=0;j<=n;j++)

{

//if length of any of the string is 0 its lcs is 0

if(i==0||j==0)

dp[i][j]=0;

//if two characters are equal

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

dp[i][j]=1+dp[i-1][j-1];

else if(X[i-1]!=Y[j-1])

dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

}

}

//lcs stores answer

string lcs="";

// Start from the right-most-bottom-most corner and

// one by one store characters in lc

int i=m,j=n;

while(i>0 && j>0)

{

if(X[i-1]==Y[j-1])

{

lcs=lcs+X[i-1];

i--;

j--;

}

else if(dp[i-1][j]>=dp[i][j-1])

i--;

else if(dp[i-1][j]<dp[i][j-1])

j--;

}

//print matrix

for(int i=0;i<=m;i++)

{

for(int j=0;j<=n;j++)

cout<<dp[i][j]<<" ";

cout<<endl;

}

//lcs will be reverse of actual answer so reverse it and print it

reverse(lcs.begin(),lcs.end());

cout<<lcs<<endl;

}

int main() {

string X="TCGCCTT";

string Y="GGGGTAACT";

LongestCommonSubsequence(X,Y);

return 0;

}