Question

Write a program that reads two strings from an input file (The first line is X, the second line is Y), compute the longest common subsequence length AND the resulting string.

You will need to write 2 methods

1) return LCS length in iterative function

// return the length of LCS. L is the 2D matrix, X, Y are the input strings, m=|X|, n=|Y|

int lcs_it(int **C, string X, string Y, int m, int n )

2) return LCS resulting string in recursive function

// return the resulting LCS string.

string backtrack(int **C, string X, string Y, int m, int n)

Hint:

Compute the length of LCS requires to use 2D matrix where the row is |X|+1, column is |Y|+1. And the 2D matrix result should be used to construct the resulting string. Below is how to create a 2D array and how to pass it to the lcs_it function.

The methods will be tested in the main method as the following.

===== main ====================

int m=X.size();

int n=Y.size();

int **C=new int*[m+1];
for (int i=0; i<m+1;++i) C[i]=new int [n+1];

int len=lcs_it(C, X, Y, m, n);

cout<<" LCS is "<<backtrack(C, X, Y, m, n)<<endl;

'

here is input.txt :

ACCGTCTTAGCGATCAACACATTTAACAACGCGCCGCACCCCCCGTCAAACGAGCTTTTGGGCTCTTGTCCTTTTACAAGCTTCACGACGCATACAGCCTTGATCAACGGTTTGATCTGTCTCCCTTCAGCTGGCTTTAAAGGACATACATATGAAGGCCTTAATAAGGTCCGGGAACTCCACATATTCGGTACTGGGCAAACCCCATGAACCACCTCAACATGAAGAGTCCGAGGACTCTCACGATCCACCAATGCAGATCGGAACTGTGCGATCGCGTAATGAGCCGAGTACTTGGTTTGTGTTTAGGTTATGGGGGCCGGGAGCCGGTTCAATATAAGGAAGTAGTTGCAGATTAGTTGTTGCGAACGGTCATAAATTTGATGGGTAAACGTGAACTTAACAAACCGTGATAGCTAATCCTATGCATCCCTTACGTGGATCGACTCGAGTACCCAGGTGAACCGACTACTTGATAACCGGAAATCGCGGTATAAAAGCGCTCACGGTCAGGAGATATACCTCCAAGCAGTAGTCTTTCTGAGCCTAGAGTAGTAAATTACAGGGACGATGTCTTTTACCGAGGCAACATTTTATTGAGAATCACATGAGGCACAGGTAAAGGCGACATCACGATCGAGATCAACCCCTACTTGTTCAAAACATTGAGAACCAGCTCTGTTTTGGAACCTAGAAAGATAACGCATCCGCTTGATATTCCACGGCTTGTCCCTCTTGTGCGGTCCATCTATCGGAGTTTCCTCCGATACGACCCGCAATGTTTCCAGGCGTACGGTACTTTATGAATACACTCGCGCTGTAACCTGTTATGTGAAACACACACGACAGAGCTTCGCGTGGGCCCAGCGACCCGGTAATACTACATCACCGCACACGACCTCGAGCAGTCTTTGCCGGCGTCCGTAAGTAGTCTAAAGTTGTGTTGATGCTTGGGGTTAAAGCTAAATCGTCCGCAGAATACGACTCTCATCCCAAT
ACCCGCACGCGCTTTGGTCTAGATTCTAGCTCCAACTTGCCTGCTAGATACTCTGTTAAAAGATGGTTTTACAACCCCCTCCTCTGTCCCTGGGGTATTATATAATACGTCGGATAGTCAGGTACAAATACAAGTGGGTGGGAATACTTTTCCTCGGATCCTAGACCACGGATTACTGCGTGGTTGACAAGAGTCGGCCCGGAGGGAAACGTGAAGGTTAGTGCAATTAAAGTCTCTAATGTGAAGCCTCCGCGAAGCGAGGAGTTTCTGAGATCGAGTACTATTTAGAGTTCGAAATCACGGCTTAACCTCACTGCCACGCATAACTTGCCGGCAATCCAGTTTTGCAACGATACTTAATTTGTGCAGCTCATCTTTGCTGTCCAGAAATAGAGCTAGTCGATCTCATCTTGCGGGTAGCCAGAAGTCCTACCGTCTCCTCCATGTAGCTTAAAAATTTCGGTGAGGATCAAAAATGATAAACGTGACAGGTAAGCTCCTACGTCTATCCTATGACCCCCGCGGCAGAATAGGTTGGTAGTGTTAGTGCGTGAGCTGGTAGAATAGAGCACACTTAGGGAAACGGGAACCGTTATGTAGGGCTGCGACACACAAAAAAGTGTTCGTTGGTAAGCTGCCTCTCCACTAAACAGGATTTCTCTGGATGATCCCATCGAAGCAAGTTACGCACCACGCCGAGGCGGACCCTGGTACTAGCTGCCCCCCCCTTTATGGGGCGCTCGTACATCAAGATGATCGCGGACTCAACCTGATTACGAGTTGTCCAAGTAGTCCAGGGTAAGAGAAACTGGAGAGA

Answer 1

The following main program in C++ does the required tasks:

#include <iostream>
#include <fstream>

using namespace std;

//LCS iterative function
int lcs_it(int **C, string X, string Y, int m, int n) {
    //Initialize first row and column to be 0
    for(int i=0;i<=n;i++) C[0][i] = 0;
    for(int i=0;i<=m;i++) C[i][0] = 0;
    
    //Iteratively construct solution
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            if(X.at(i-1) == Y.at(j-1)) C[i][j] = C[i-1][j-1]+1;
            else if(C[i-1][j]>C[i][j-1]) C[i][j] = C[i-1][j];
            else C[i][j] = C[i][j-1];
        }
    }
    return C[m][n];
}

string backtrack(int **C, string X, string Y, int m, int n) {
    //C now contains the required length values
    //Just construct the LCS from it
    //Start from end
    string lcs = "";
    int i=m,j=n;
    while(i>0 && j>0) {
        if(X.at(i-1) == Y.at(j-1)) {lcs.insert(0,1,X.at(i-1));i--;j--;}
        else if(C[i][j] == C[i-1][j]) {i--;}
        else j--;
    }
    return lcs;
}
int main()
{
    ifstream f1;
    f1.open("input.txt");
    string X;
    string Y;
    getline(f1,X);
    getline(f1,Y);
    int m = X.size();
    int n = Y.size();
    int **C=new int*[m+1];
    for (int i=0; i<m+1;++i) C[i]=new int [n+1];

    int len = lcs_it(C, X, Y, m, n);
    cout <<len << endl;
    
    cout<<" LCS is "<< backtrack(C, X, Y, m, n) <<endl;
    return 0;
}

Create a file input.txt in the same folder as the above cpp program with the contents given iin the question:

ACCGTCTTAGCGATCAACACATTTAACAACGCGCCGCACCCCCCGTCAAACGAGCTTTTGGGCTCTTGTCCTTTTACAAGCTTCACGACGCATACAGCCTTGATCAACGGTTTGATCTGTCTCCCTTCAGCTGGCTTTAAAGGACATACATATGAAGGCCTTAATAAGGTCCGGGAACTCCACATATTCGGTACTGGGCAAACCCCATGAACCACCTCAACATGAAGAGTCCGAGGACTCTCACGATCCACCAATGCAGATCGGAACTGTGCGATCGCGTAATGAGCCGAGTACTTGGTTTGTGTTTAGGTTATGGGGGCCGGGAGCCGGTTCAATATAAGGAAGTAGTTGCAGATTAGTTGTTGCGAACGGTCATAAATTTGATGGGTAAACGTGAACTTAACAAACCGTGATAGCTAATCCTATGCATCCCTTACGTGGATCGACTCGAGTACCCAGGTGAACCGACTACTTGATAACCGGAAATCGCGGTATAAAAGCGCTCACGGTCAGGAGATATACCTCCAAGCAGTAGTCTTTCTGAGCCTAGAGTAGTAAATTACAGGGACGATGTCTTTTACCGAGGCAACATTTTATTGAGAATCACATGAGGCACAGGTAAAGGCGACATCACGATCGAGATCAACCCCTACTTGTTCAAAACATTGAGAACCAGCTCTGTTTTGGAACCTAGAAAGATAACGCATCCGCTTGATATTCCACGGCTTGTCCCTCTTGTGCGGTCCATCTATCGGAGTTTCCTCCGATACGACCCGCAATGTTTCCAGGCGTACGGTACTTTATGAATACACTCGCGCTGTAACCTGTTATGTGAAACACACACGACAGAGCTTCGCGTGGGCCCAGCGACCCGGTAATACTACATCACCGCACACGACCTCGAGCAGTCTTTGCCGGCGTCCGTAAGTAGTCTAAAGTTGTGTTGATGCTTGGGGTTAAAGCTAAATCGTCCGCAGAATACGACTCTCATCCCAAT
ACCCGCACGCGCTTTGGTCTAGATTCTAGCTCCAACTTGCCTGCTAGATACTCTGTTAAAAGATGGTTTTACAACCCCCTCCTCTGTCCCTGGGGTATTATATAATACGTCGGATAGTCAGGTACAAATACAAGTGGGTGGGAATACTTTTCCTCGGATCCTAGACCACGGATTACTGCGTGGTTGACAAGAGTCGGCCCGGAGGGAAACGTGAAGGTTAGTGCAATTAAAGTCTCTAATGTGAAGCCTCCGCGAAGCGAGGAGTTTCTGAGATCGAGTACTATTTAGAGTTCGAAATCACGGCTTAACCTCACTGCCACGCATAACTTGCCGGCAATCCAGTTTTGCAACGATACTTAATTTGTGCAGCTCATCTTTGCTGTCCAGAAATAGAGCTAGTCGATCTCATCTTGCGGGTAGCCAGAAGTCCTACCGTCTCCTCCATGTAGCTTAAAAATTTCGGTGAGGATCAAAAATGATAAACGTGACAGGTAAGCTCCTACGTCTATCCTATGACCCCCGCGGCAGAATAGGTTGGTAGTGTTAGTGCGTGAGCTGGTAGAATAGAGCACACTTAGGGAAACGGGAACCGTTATGTAGGGCTGCGACACACAAAAAAGTGTTCGTTGGTAAGCTGCCTCTCCACTAAACAGGATTTCTCTGGATGATCCCATCGAAGCAAGTTACGCACCACGCCGAGGCGGACCCTGGTACTAGCTGCCCCCCCCTTTATGGGGCGCTCGTACATCAAGATGATCGCGGACTCAACCTGATTACGAGTTGTCCAAGTAGTCCAGGGTAAGAGAAACTGGAGAGA

The output :

573
 LCS is ACCGTTTGGTCAACACTCAACGCGCGACCGTAAAGATGGTTTTACAACCCCCTCCCTGTCCGGTTTATTTCTCTAGTCAGGACAAATAAAGGGGTGGGAATACTTTCTCGGACCAGACCACTACTGGTGGTTGACAAGAGTCGGCGGGGGAAAGGAAGGTTGTGTTAGTTATGGGCCGGAGCGAGGAGTTTGAGATCGAGTCTATTTGATTCGAATCACGGTTAACCTATGCACCTACTTGCCGATCCAGTGAACGACTATTGTACCATCGCGTAAAAAGGCTAGTCGATATCCTCCAAGCTAGTCTTCTGAGCTAAAAATTCGGGAGATCAAAAATATAAACTGACAGGTAAGCCTACGATCAGACCCCCCGCAAAATTGGAGTGTTTTGGCTAGAAAGAGCACCTTGAAACGGGCCTTTGTGGGTCCACACAGTTTCTGTAAGCTGTTCCACTACGGTCTTATGATCATCGGCAAGTTAGCACCACGCGAGGCGGACCCGGTATACTCCCCCCACGCTCGACATCTTGCGGCTCCTGATTAAGTTGTGTGTCGGGTAAAGAAATGGAGAGA

For LCS length finding standard LCS dynamic procedure is followed. It checks the values at that index. If they are equal then LCS length will increment, otherwise either the top or left value is copied. For constructing the LCS, start from the end and if the values at a certain index are equal then move to the diagonally opposite element and insert the character at the front of the lcs and the reverse process continues. It is advised to run a few short examples by hand to see why the algorithm works.