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].

  lcs-backtrack-wiki

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++ implementation –
 

Download   Run Code

Output:

MJAU


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

Above code doesn’t generate all LCS 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++ implementation –
 

Download   Run Code

Output:

BCAB
BCBA
BDAB

 

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

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz