Longest Common Subsequence

Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. 

We would solve this problem by using recursion as it is easier to understand but the downside is that it is not optimal.

#include <iostream>
using namespace std;
 
int max(int a, int b);
int lcs( char *X, char *Y, int m, int n )
{
    if (m == 0 || n == 0)
        return 0;
    if (X[m-1] == Y[n-1])
        return 1 + lcs(X, Y, m-1, n-1);
    else
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
int max(int a, int b)
{
    return (a > b)? a : b;
}

int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int m = strlen(X);
    int n = strlen(Y);
    cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ;
    return 0;
}
 

Time complexity of the above recursive approach is O(2^n) in worst case and worst case happens when all characters of X and Y mismatch i.e., length of LCS is 0. 

Another approach to the same problem is by using Tabulation Method.

#include<iostream>
using namespace std;
 
int max(int a, int b);
 

int lcs( char *X, char *Y, int m, int n )
{
    int L[m + 1][n + 1];
    int i, j;
    for (i = 0; i <= m; i++)
    {
        for (j = 0; j <= n; j++)
        {
        if (i == 0 || j == 0)
            L[i][j] = 0;
     
        else if (X[i - 1] == Y[j - 1])
            L[i][j] = L[i - 1][j - 1] + 1;
     
        else
            L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
     
    return L[m][n];
}
int max(int a, int b)
{
    return (a > b)? a : b;
}
int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
     
    int m = strlen(X);
    int n = strlen(Y);
     
    cout << "Length of LCS is "
        << lcs( X, Y, m, n );
     
    return 0;
}

Time Complexity of the above implementation is O(mn) which is much better than the worst-case time complexity of Recursive implementation.