Question

I need this using C++.

In this project, you will implement the dynamic programming-based solution to find the longest common subsequence (LCS) of two sequences. Your inputs will be the two sequences (as Strings) and the outputs are the longest common subsequence (printed as a String) and the final matrix (printed as a two-dimensional array) depicting the length of the longest common subsequences (as shown in the slides) for all possible subsequences of the two input sequences. The two input sequences to be used by each student are shown below. The LCS expected for the two sequences is also shown. Row Sequence Column Sequence GGGGTAACT LCS TCT TCGCCTT Asample output is shown below Column Sequence: ATGCGGGG A word document containing the following: Row Sequence: ou Sequence: ATTAGTGGA Submission (through Canvas: (i) entire code (ii) the outputs showing the final dynamic programming table (of the lengths of the longest common subsequences of all possible subsequences of the two input strings) and the longest common subsequence 1 2 2 2 2 2 2 2 2 0 1 2 2 2 2 2 2 2 2 0 1 2 2 2 2 2 2 2 2 0 1 2 3 33 3 33 3 0 1 2 3 33 3 3 3 3 0 1 2 33 4 4 4 4 4 0 1 2 3 3 4 4 4 4 4 1 2 3 4 4 4 4 4 5 0 1 2 3 4 5 5555 0 1 2 3 4 55555 LCS: ATGGC

Answer 1

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;
}