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

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

Output:

MJAU

## Java

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.

Output:

BCAB
BCBA
BDAB

## Java

Output:

BCAB
BCBA
BDAB

(2 votes, average: 5.00 out of 5)

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 🙂

Subscribe
Notify of
Guest

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

Guest