Longest Common Subsequence | Finding all LCS

Given two sequences, print all the possible longest common subsequences present in them.


 

For example,


Input:  X = “XMJYAUZ”, Y = “MZJAWXU”
Output: MJAU
 

Input:  X = “ABCBDAB”, Y = “BDCABA”
Output: BCAB, BCBA, BDAB

 
In previous post we have discussed how to find the length of Longest Common Subsequence. In this post we will discuss how to print Longest Common Subsequence itself.
 

 
Let X be “XMJYAUZ” and Y be “MZJAWXU”. The longest common subsequence between X and Y is “MJAU”. The table below shows the lengths of the longest common subsequences between prefixes of X and Y. The i’th row and j’th column shows the length of the LCS of substring X[0..i-1] and Y[0..j-1].

  longest common subsequence

The highlighted numbers show the path one should follow from the bottom right to the top left corner, when reading out an LCS. If the current characters in X and Y are equal (shown in bold), then they are part of the LCS and we move diagonally. If the current characters in X and Y are different, we go up or left, depending on which cell has a higher number. This corresponds to either taking the LCS between X[0..i-2], Y[0..j-1], or X[0..i-1], Y[0..j-2].
 

Below code fills lookup table in bottom-up manner and then recursively find LCS in top-down manner using values in lookup table..

C++

Download   Run Code

Output:

MJAU

Java

Download   Run Code

Output:

MJAU

 

How can we modify the code so it prints all possible LCS?

Above code doesn’t generate all Longest Common Subsequence of given sequences. It will always print one LCS. The problem with above code is when the last character of X and Y are different, it discards either last character of X or last character of Y based on the value of the top or left cell to the current cell. But what if LCS is also possible with the discarded character?

The idea remains the same except if the top cell is equal to the left cell, then we consider both characters else we go in direction of greater value.

C++

Download   Run Code

Output:

BCAB
BCBA
BDAB

Java

Download   Run Code

Output:

BCAB
BCBA
BDAB

 
References: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
anudeex
Guest

Time complexity of above code for printing all possible LCS??

kishore
Guest

Hey admin,getting forbidden error while clicking LCS problem(previous post-link), please rectify it.

Birender Singh
Guest

Thanks for sharing problem and solution. I’ve attempted using HashMap (String, ArrayList) in Java 8. Here is the link for refernce, welcoming inputs !
https://github.com/birender-s/data-structures/blob/master/java-lib/src/main/java/com/example/java_lib/DP/LongestCommonSequence.java