Implement the given code to solve the Longest Common Subsequence problem by dynamic programming in C++

You need to implement the basic algorithm which takes O(nm) time & space to find the subsequence. Your algorithm should identify the longest common sub-sequence (and not just give its length).

Program Input: your program should prompt the user to enter two strings from keyboard, representing two DNA sequences on alphabete of {A, C, G, T}.

Error checking: before executing the algorithm, your program should check both strings to ensure only acceptable DNA letters (A, C, G, T) are entered. Do not run the algorithm if they contain any errors inside. In the event of an error, indicate how many characters are illegal, and show the original string with the illegal letters highlighted, for example show an error message of the following type:

Assignment6.cpp (Given. This is the driver program. Don't change it, use it to check your LCS.cpp)

#include "LCS.h" #include #include using namespace std; //This function used to print the table contents void printLengthTable(int** C, int m, int n); void printArrowTable(char** B, int m, int n); int main() { string strX, strY; cout > strX; cout > strY; //validate the input two strings if(validate(strX, strY)== false) { return 0; } int m = strX.length(); int n = strY.length(); //declare two dynamic 2-Dimensional array of variable length //C is (m+1)X(n+1) and B is m X n int** C; char** B; initLCSTable(&C, &B, m, n); fillLCSTable(strX, strY, C, B); cout  
LCS.h (Given. But feel free to add any auxillary functions which you think can make your task easier)
 
#ifndef LCS_H #define LCS_H #include using namespace std; bool validate(string strX, string strY); void initLCSTable(int*** C, char*** B, int m, int n); void fillLCSTable(string str1, string str2, int** C, char** B); string findLCS(string str1, char** B, int m, int n); void freeLCSTable(int** C, char** B, int m); #endif 
 
LCS.cpp (Partialy given, need to add your own code)
 
#include "LCS.h" #include using namespace std; //******************************************************************* //This function validate the two input string X and Y respectively. //It return true if both are valid DNA sequence; otherwise it return //false and print the relevant error information on screen. bool validate(string strX, string strY) { //Add your own code here //---- //---- } //******************************************************************* //This function initializes arrays C[m+1][n+1] and B[m][n] and fill //the first row and first column of C with zeros. Note: int*** C refers //to a pointer points to the 2D integer array void initLCSTable(int*** C, char*** B, int m, int n) { //Add your own code here //---- //---- } //******************************************************************* //This function fill 2D array C and B as the LCS algorithm shows //For array B, use 'X' for diagonal arrow, 'L' for left arrow and //'U' for up arrow void fillLCSTable(string strX, string strY, int** C, char** B) { for(int row = 0; row  
}
 
Test Input1:
 
ATCCGACAAC
 
ATCGCATCTT
 
Test Ouput1:
 
  Input contains error Error in String #1 : aacgttcOgMa Error in String #2: ggataccasat Program Output: your (1) The length of the longest subsequence (2) The actual subsequence string (3) The dynamic subsequence table C and IB See below for a sample output. Note: Table B represents the arrow table, letter X refers to the diagnol arrow, where letter L' refers to left arrow and letter U refers to up arrow. program should output the following on screen: The LCS is: ATCGCAC Length 7 Table C 0 1 2 2 2 2 2 2 2 2 2 0 1 2 333 333 3 3 01 233 4 4 4 4 4 4 0 1 2 3 4 4 4 4 4 4 4 0 1 2 3 4 4 5 5 5 5 5 0 1 2 3 4 5 5 5 6 6 6 0 1 2 3 45 6 6 6 6 6 01 2 3 45 6 6 6 6 6 0 1 2 345 66777 Table B UUXLXLLXLL XU UUUX L L L L X U UUUXUUU U UUXUX U UX L L  Input contains error Error in String #1 : aacgttcOgMa Error in String #2: ggataccasat Program Output: your (1) The length of the longest subsequence (2) The actual subsequence string (3) The dynamic subsequence table C and IB See below for a sample output. Note: Table B represents the arrow table, letter X refers to the diagnol arrow, where letter L' refers to left arrow and letter U refers to up arrow. program should output the following on screen: The LCS is: ATCGCAC Length 7 Table C 0 1 2 2 2 2 2 2 2 2 2 0 1 2 333 333 3 3 01 233 4 4 4 4 4 4 0 1 2 3 4 4 4 4 4 4 4 0 1 2 3 4 4 5 5 5 5 5 0 1 2 3 4 5 5 5 6 6 6 0 1 2 3 45 6 6 6 6 6 01 2 3 45 6 6 6 6 6 0 1 2 345 66777 Table B UUXLXLLXLL XU UUUX L L L L X U UUUXUUU U UUXUX U UX L L