Longest Common Subsequence

By | October 13, 2015

Longest Common Subsequence (LCS) – Dynamic Programming

Longest Common Subsequence Problem Statement:

Given two sequences (strings or arrays) A and B, 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, “coe”, “ksa”, “dek”, “code”, ‘”kaksa”, .. etc are subsequences of “code kaksha”.
A string of length n has 2n different possible subsequences.

Longest Common Subsequence Problem Example:

A= "Code Kaksha"
B= "Cloud Kaksha is the Best"

The length of Longest common subsequence(LCS) is 10 for “Cod Kaksha”

Longest Common Subsequence Solution:

Video Explanation:

State of DP:

let lcs[i][j]  store the length of LCS of A[0…i-1] and B[0…j-1].

Recursion for DP:

If last characters of both sequences match (or A[m-1] == B[n-1]) then
lcs(m,n) = 1 + lcs(m-1, n-1).

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
lcs(m, n) = MAX ( lcs(m-1,n), lcs(m, n-1)).

How it works:

  1. Consider the input strings “Winner” and “Racer”. Last characters match for the strings. So length of LCS can be written as:
    LCS(“Winner”, “Racer”) = 1 + LCS(“Winne”, “Race”).
  2. Consider the input strings “Winner” and “Today”. Last characters do not match for the strings. So length of LCS can be written as:
    LCS(“Winner”, “Today”) = MAX ( LCS(“Winne”, “Today”), LCS(“Winner”, “Toda”) ).

Longest Common Subsequence Solution:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int LCS(string A, string B)
{
   int lcs[A.length()+1][B.length()+1];
   
   for(int i=0; i<=A.length(); ++i)
      for(int j=0; j<=B.length(); ++j)
      {
         /*One string is of length 0*/
         if(i==0 || j==0)
            lcs[i][j]=0;
         /*When last elements are equal*/	
         else if(A[i-1]==B[j-1])
            lcs[i][j]=lcs[i-1][j-1] + 1;
         /*When last elements are not equal*/	
         else
            lcs[i][j]= max(lcs[i-1][j] ,lcs[i][j-1] );
      }
   return lcs[A.length()][B.length()];
}

/* Driver program to test above function */
int main()
{
  string  A= "Code Kaksha";
  string  B= "Cloud Kaksha is the Best";
  
  /*LCS is "Cod Kaksha"*/
  cout<<"Length of LCS is \n"<<LCS(A, B);
  return 0;
}

Output:

Length of LCS is 
10

Time Complexity: O(N2)
Auxiliary Space: O(N2)

An application of this algorithm is the Spoj ADFRUITS question. To understand how solution works, read the question and then refer to Spoj ADFRUITS solution.