Programming Practice: Calculate and print the LCS

gistfile1.cpp

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// get the LCS from the matrix
string get_LCS(vector<vector<char> > & S, string & X, int i, int j) {
    string result;
    if (i == 0 || j == 0)
        return result; // empty string
    if(S[i][j] == 's') {
        return print_LCS(S, X, i-1, j-1) + X[i-1];
    } else if (S[i][j] == 'j') {
        return print_LCS(S, X, i, j-1);
    } else {
        return print_LCS(S, X, i-1, j);
    }
}

void calc_LCS(string & X, string & Y) {
    
    // this is C[i][j]
    // the longest common subsequence between X[1..i] and Y[1..i]
    // all initialized to 0
    vector<vector<int> > C;  // 
    vector<vector<char> > S; // position of LCS
    C.resize(X.size()+1);
    S.resize(X.size()+1);
    for(int i = 0; i <= X.size(); ++i) {
        C[i].resize(Y.size()+1);
        S[i].resize(Y.size()+1);
        for(int j = 0; j <= Y.size(); ++j) {
            C[i][j] = 0;
            S[i][j] = 's';
        }
    }

    // compute C[i][j] for all i and j
    for(int i = 1; i <= X.size(); ++i) {
        for(int j = 1; j <= Y.size(); ++j) {

            if(X[i-1] == Y[j-1]) {
                C[i][j] = C[i-1][j-1] + 1;
                S[i][j] = 's'; // X[i] or Y[i] is an item of LCS  
            } else if ( C[i-1][j] > C[i][j-1] ) {
                C[i][j] = C[i-1][j];            
                S[i][j] = 'i';  // LCS is same as LCS of X[1..i-1]       
            } else {
                C[i][j] = C[i][j-1];
                S[i][j] = 'j'; // LCS is same as LCS of Y[1..j-1]
            }
        }
    }

    // print
    cout << "LCS: " << print_LCS(S, X, X.size(), Y.size()) << endl;
}

int main() {
    string X = "ACCGGGTTAC";
    string Y = "AGGACCA";
    cout << "X: " << X << endl;
    cout << "Y: " << Y << endl;
    calc_LCS(X,Y);
    return 0;
}