Given two sequences, print all longest subsequence present in both of them.
Examples:
Input: string X = "AGTGATG" string Y = "GTTAG" Output: GTAG GTTG Input: string X = "AATCC" string Y = "ACACG" Output: ACC AAC Input: 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 character 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 implementation of above idea –
C++
/* Dynamic Programming implementation of LCS problem */#include <bits/stdc++.h>using namespace std;// Maximum string length#define N 100int 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;} |
Java
/* Dynamic Programming implementation of LCS problem */import java.util.*;class GFG{// Maximum String lengthstatic int N = 100;static int [][]L = new int[N][N];/* Returns set containing all LCS for X[0..m-1], Y[0..n-1] */static Set<String> findLCS(String X, String Y, int m, int n){ // construct a set to store possible LCS Set<String> s = new HashSet<>(); // If we reaches end of either String, // return a empty set if (m == 0 || n == 0) { s.add(""); return s; } // If the last characters of X and Y are same if (X.charAt(m - 1) == Y.charAt(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.add(str + X.charAt(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.addAll(tmp); } } return s;}/* Returns length of LCS for X[0..m-1], Y[0..n-1] */static 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.charAt(i - 1) == Y.charAt(j - 1)) L[i][j] = L[i - 1][j - 1] + 1; else L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]); } } return L[m][n];}// Driver Codepublic static void main(String[] args){ String X = "AGTGATG"; String Y = "GTTAG"; int m = X.length(); int n = Y.length(); System.out.println("LCS length is " + LCS(X, Y, m, n)); Set<String> s = findLCS(X, Y, m, n); for (String str : s) System.out.println(str);}}// This code is contributed by 29AjayKumar |
Python3
# Dynamic Programming implementation of LCS problem# Maximum string lengthN = 100L = [[0 for i in range(N)] for j in range(N)]# Returns set containing all LCS # for X[0..m-1], Y[0..n-1]def findLCS(x, y, m, n): # construct a set to store possible LCS s = set() # If we reaches end of either string, return # a empty set if m == 0 or n == 0: s.add("") 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 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 in tmp: s.add(string + 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]: 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] for i in tmp: s.add(i) return s# Returns length of LCS for X[0..m-1], Y[0..n-1]def LCS(x, y, m, n): # Build L[m+1][n+1] in bottom up fashion for i in range(m + 1): for j in range(n + 1): if i == 0 or 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 Codeif __name__ == "__main__": x = "AGTGATG" y = "GTTAG" m = len(x) n = len(y) print("LCS length is", LCS(x, y, m, n)) s = findLCS(x, y, m, n) for i in s: print(i)# This code is contributed by# sanjeev2552 |
C#
// Dynamic Programming implementation // of LCS problem using System;using System.Collections.Generic; class GFG{// Maximum String lengthstatic int N = 100;static int [,]L = new int[N, N];/* Returns set containing all LCS for X[0..m-1], Y[0..n-1] */static HashSet<String> findLCS(String X, String Y, int m, int n){ // construct a set to store possible LCS HashSet<String> s = new HashSet<String>(); // If we reaches end of either String, // return a empty set if (m == 0 || n == 0) { s.Add(""); 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 HashSet<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]. foreach (String str in tmp) s.Add(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]) { HashSet<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] foreach (String str in tmp) s.Add(str); } } return s;}/* Returns length of LCS for X[0..m-1], Y[0..n-1] */static 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] = Math.Max(L[i - 1, j], L[i, j - 1]); } } return L[m, n];}// Driver Codepublic static void Main(String[] args){ String X = "AGTGATG"; String Y = "GTTAG"; int m = X.Length; int n = Y.Length; Console.WriteLine("LCS length is " + LCS(X, Y, m, n)); HashSet<String> s = findLCS(X, Y, m, n); foreach (String str in s) Console.WriteLine(str);}} // This code is contributed by Rajput-Ji |
Javascript
<script>/* Dynamic Programming implementation of LCS problem */// Maximum String lengthlet N = 100;let L = new Array(N);for(let i=0;i<N;i++){ L[i]=new Array(N); }/* Returns set containing all LCS for X[0..m-1], Y[0..n-1] */function findLCS(X,Y,m,n){ // construct a set to store possible LCS let s = new Set(); // If we reaches end of either String, // return a empty set if (m == 0 || n == 0) { s.add(""); 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 let 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 (let str of tmp.values()) s.add(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]) { let 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] for (let item of tmp.values()) s.add(item) } } return s;}/* Returns length of LCS for X[0..m-1], Y[0..n-1] */function LCS(X,Y,m,n){ // Build L[m+1][n+1] in bottom up fashion for (let i = 0; i <= m; i++) { for (let 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] = Math.max(L[i - 1][j], L[i][j - 1]); } } return L[m][n];}// Driver Codelet X = "AGTGATG";let Y = "GTTAG";let m = X.length;let n = Y.length;document.write("LCS length is " + LCS(X, Y, m, n)+"<br>");let s = findLCS(X, Y, m, n);for (let str of s.values()) document.write(str+"<br>");// This code is contributed by rag2127</script> |
Output:
LCS length is 4 GTAG GTTG
Time Complexity: It will be exponential because we are using recursion to find all possible LCS.
Space Complexity: O(n*n)
References: Wikibooks – Reading out all LCSs
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
