main.cpp

#include <iostream>
#include <vector>

using namespace std;

/*
    What is the longest common subsequence problem?
    The longest common subsequence (LCS) problem is the problem of
    finding the longest subsequence common to all sequences in a set of
    sequences.

    Applications: DNA Analise of two or more different organisms
                  A DNA is compound by a sequence of molecules, called bases:
                  Adenine, Chemin, guanine and cytosine.
    Given two DNA:
    S1 = ACCGTGGAAAAGGTTAAGGCCAGGATTTAACCGCGGGC
    S2 = ACCGCGGTTTAATCCGGATAGGTTGAAATGGTTGAAAC

    Is possible to answer, how much identical are those DNA, and so on.

    For abcd and acd, the answer is LCS(s1, s2) = acd

    Algorithm:
    Given two strings
    if s1m == s2n, must do: s1m - 1, s2n - 1 + s1m or s2m.
    otherwise: check what is the longest, s1m - 1 or s2m - 1.

    c(i,j) = { 0, if i = 0 or j = 0 }
             { c(i - 1, j - 1) + 1, if i == 1 }
             { max (c(i - 1, j), c(i, j - 1), if i != j}

    Table:
    x = BDCABA, Y = ABCBDAB
        yj  A  B  C  B  D  A  B
    xi   0  0  0  0  0  0  0  0
    B    0  0  1  1  1  1  1  1
    D    0  0  1  1  1  2  2  2
    C    0  0  1  2  2  2  2  2
    A    0  1  1  2  2  2  3  3
    B    0  1  2  2  3  3  3  4
    A    0  1  2  2  3  3  4  4
*/

// There are two cases, when the end of words matches and when it doesn't match,
// so it takes the maximum between the string 1 or string 2 by decreasing its size.
// Example: STR1: ABCD, STR2: AB.
// First call:

int result = 0;
// Recursive solution for LCS
int lcsRecursive(string s1, string s2, int indexS1, int indexS2) {
    if(indexS1 == 0 || indexS2 == 0) // base case
        return 0; // strings are empty, any char matches
    else {
        // If the end of the strings are equal, then return 1 + the sum of what is left
        if(s1[indexS1] == s2[indexS2]) {
            return 1 + lcsRecursive(s1, s2, indexS1 - 1, indexS2 - 1);
        } else {
            // if they are not equal, then, return maximum both from the string 1 or string 2
            return max(lcsRecursive(s1, s2, indexS1 - 1, indexS2), lcsRecursive(s1, s2, indexS1, indexS2 - 1));
        }
    }
}

// LCS Top down Dynamic Programming
vector<vector<int> > table;
int lcsRecursiveDP(string s1, string s2, int indexS1, int indexS2) {
    if(table[indexS1][indexS2])
        return table[indexS1][indexS2];
    else {
        if(indexS1 == 0 || indexS2 == 0)
            table[indexS1][indexS2] = 0;
        else {
            if(s1[indexS1] == s2[indexS2])
                table[indexS1][indexS2] = 1 + lcsRecursiveDP(s1,s2, indexS1 - 1, indexS2 - 1);
            else
                table[indexS1][indexS2] = max(lcsRecursiveDP(s1,s2,indexS1 - 1,indexS2), lcsRecursiveDP(s1,s2,indexS1, indexS2 - 1));
        }
        return table[indexS1][indexS2];
    }
}

string lcs(string s1, string s2) {
    int xSize = (int)s1.size(); // Getting size of string 1
    int ySize = (int)s2.size(); // Getting size of string 2


    int table[xSize + 1][ySize + 1]; // Creating table of size xSize + 1 and ySize + 1 so that the table is going to have either a free row and col to insert 0

    // Inserting 0 in the first row
    for(int i = 0; i < ySize + 1; i++) {
        table[0][i] = 0;
    }

    // Inserting 0 in the first col
    for(int i = 0; i < xSize + 1; i++) {
        table[i][0] = 0;
    }

    // Filling the table
    for(int i = 1; i <= xSize; i++) {
        for(int j = 1; j <= ySize; j++) {
            if(s1[i - 1] == s2[j - 1]) { // if S1[i] == s2[i], get table[i - 1, j - 1] (element of diagonal) and sum to 1
                table[i][j] = table[i - 1][j - 1] + 1;
            } else { // Otherwise, get the maximum, can be either table[i - 1][j] or table[i][j - 1]
                table[i][j] = table[i - 1][j] > table[i][j - 1] ? table[i - 1][j] : table[i][j - 1];
            }
        }
    }

    // Printing table

    for (int i = 0; i < xSize + 1; i++) {
        for(int j = 0; j < ySize + 1; j++) {
            cout << table[i][j] << " ";
        }
        cout << endl;
    }

    /* Finding what is the sequence
        Steps:
        Traverse the 2D array starting from L[m][n]. Do following for every cell L[i][j]
            a) If characters (in X and Y) corresponding to L[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
            b) Else compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.

    */
    string stresult = "";
    int i = xSize, j = ySize;
    while(j > 0 && i > 0) {
        if(s1[i - 1] == s2[j - 1]) {
            stresult+=s1[i - 1];
            i--; j--;
        } else if (table[i - 1][j] > table[i][j - 1])
            i--;
        else
            j--;
    }

    return stresult;
}

int main()
{
    cout << lcsRecursive("ABCB", "BDCAB", 4, 5) << endl;
    table.assign(4, vector<int>(5,0));
    cout << lcsRecursiveDP("ABCB", "BDCAB", 4, 5) << endl;
    cout << lcs("AGGTAB", "GXTXAYB") << endl;
    return 0;
}