Given two sequences, print all longest subsequence present in both of them.

Examples:

Input:string X = "AGTGATG" string Y = "GTTAG"Output:GTAG GTTGInput:string X = "AATCC" string Y = "ACACG"Output:ACC AACInput:string X = "ABCBDAB" string Y = "BDCABA"Output:BCAB BCBA BDAB

We have discussed Longest Common Subsequence (LCS) problem here. The function discussed there was mainly to find the length of LCS. We have also discussed how to print the longest subsequence here. But as LCS for two strings is not unique, in this post we will print out all the possible solutions to LCS problem.

Following is detailed algorithm to print the all LCS.

We construct L[m+1][n+1] table as discussed in the previous post and traverse the 2D array starting from L[m][n]. For current cell L[i][j] in the matrix,

a) If the last characters of X and Y are same (i.e. X[i-1] == Y[j-1]), then the charcater must be present in all LCS of substring X[0…i-1] and Y[0..j-1]. We simply recurse for L[i-1][j-1] in the matrix and append current character to all LCS possible of substring X[0…i-2] and Y[0..j-2].

b) If the last characters of X and Y are not same (i.e. X[i-1] != Y[j-1]), then LCS can be constructed from either top side of the matrix (i.e. L[i-1][j]) or from left side of matrix (i.e. L[i][j-1]) depending upon which value is greater. If both the values are equal(i.e. L[i-1][j] == L[i][j-1]), then it will be constructed from both sides of matrix. So based on values at L[i-1][j] and L[i][j-1], we go in direction of greater value or go in both directions if the values are equal.

Below is recursive C++ implementation of above idea –

`/* Dynamic Programming implementation of LCS problem */` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// Maximum string length ` `#define N 100 ` ` ` `int` `L[N][N]; ` ` ` `/* Returns set containing all LCS for X[0..m-1], Y[0..n-1] */` `set<string> findLCS(string X, string Y, ` `int` `m, ` `int` `n) ` `{ ` ` ` `// construct a set to store possible LCS ` ` ` `set<string> s; ` ` ` ` ` `// If we reaches end of either string, return ` ` ` `// a empty set ` ` ` `if` `(m == 0 || n == 0) ` ` ` `{ ` ` ` `s.insert(` `""` `); ` ` ` `return` `s; ` ` ` `} ` ` ` ` ` `// If the last characters of X and Y are same ` ` ` `if` `(X[m - 1] == Y[n - 1]) ` ` ` `{ ` ` ` `// recurse for X[0..m-2] and Y[0..n-2] in ` ` ` `// the matrix ` ` ` `set<string> tmp = findLCS(X, Y, m - 1, n - 1); ` ` ` ` ` `// append current character to all possible LCS ` ` ` `// of substring X[0..m-2] and Y[0..n-2]. ` ` ` `for` `(string str : tmp) ` ` ` `s.insert(str + X[m - 1]); ` ` ` `} ` ` ` ` ` `// If the last characters of X and Y are not same ` ` ` `else` ` ` `{ ` ` ` `// If LCS can be constructed from top side of ` ` ` `// the matrix, recurse for X[0..m-2] and Y[0..n-1] ` ` ` `if` `(L[m - 1][n] >= L[m][n - 1]) ` ` ` `s = findLCS(X, Y, m - 1, n); ` ` ` ` ` `// If LCS can be constructed from left side of ` ` ` `// the matrix, recurse for X[0..m-1] and Y[0..n-2] ` ` ` `if` `(L[m][n - 1] >= L[m - 1][n]) ` ` ` `{ ` ` ` `set<string> tmp = findLCS(X, Y, m, n - 1); ` ` ` ` ` `// merge two sets if L[m-1][n] == L[m][n-1] ` ` ` `// Note s will be empty if L[m-1][n] != L[m][n-1] ` ` ` `s.insert(tmp.begin(), tmp.end()); ` ` ` `} ` ` ` `} ` ` ` `return` `s; ` `} ` ` ` `/* Returns length of LCS for X[0..m-1], Y[0..n-1] */` `int` `LCS(string X, string Y, ` `int` `m, ` `int` `n) ` `{ ` ` ` `// Build L[m+1][n+1] in bottom up fashion ` ` ` `for` `(` `int` `i = 0; i <= m; i++) ` ` ` `{ ` ` ` `for` `(` `int` `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]; ` `} ` ` ` `/* Driver program to test above function */` `int` `main() ` `{ ` ` ` `string X = ` `"AGTGATG"` `; ` ` ` `string Y = ` `"GTTAG"` `; ` ` ` `int` `m = X.length(); ` ` ` `int` `n = Y.length(); ` ` ` ` ` `cout << ` `"LCS length is "` `<< LCS(X, Y, m, n) << endl; ` ` ` ` ` `set<string> s = findLCS(X, Y, m, n); ` ` ` ` ` `for` `(string str : s) ` ` ` `cout << str << endl; ` ` ` ` ` `return` `0; ` `} ` |

Output:

GTAG GTTG

References: Wikibooks – Reading out all LCSs

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments