Print all longest common sub-sequences in lexicographical order - GeeksforGeeks
You are given two strings.Now you have to print all longest common sub-sequences in lexicographical order?
https://stackoverflow.com/questions/16848704/all-possible-lcslongest-common-subsequence-of-two-strings
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
Read full article from Print all longest common sub-sequences in lexicographical order - GeeksforGeeks
You are given two strings.Now you have to print all longest common sub-sequences in lexicographical order?
This problem is an extension of longest common subsequence. We first find length of LCS and store all LCS in 2D table using Memoization (or Dynamic Programming). Then we search all characters from ‘a’ to ‘z’ (to output sorted order) in both strings. If a character is found in both strings and current positions of character lead to LCS, we recursively search all occurrences with current LCS length plus 1.
// length of lcsint lcslen = 0;// dp matrix to store result of sub calls for lcsint dp[MAX][MAX];// A memoization based function that returns LCS of// str1[i..len1-1] and str2[j..len2-1]int lcs(string str1, string str2, int len1, int len2, int i, int j){ int &ret = dp[i][j]; // base condition if (i==len1 || j==len2) return ret = 0; // if lcs has been computed if (ret != -1) return ret; ret = 0; // if characters are same return previous + 1 else // max of two sequences after removing i'th and j'th // char one by one if (str1[i] == str2[j]) ret = 1 + lcs(str1, str2, len1, len2, i+1, j+1); else ret = max(lcs(str1, str2, len1, len2, i+1, j), lcs(str1, str2, len1, len2, i, j+1)); return ret;}// Function to print all routes common sub-sequences of// length lcslenvoid printAll(string str1, string str2, int len1, int len2, char data[], int indx1, int indx2, int currlcs){ // if currlcs is equal to lcslen then print it if (currlcs == lcslen) { data[currlcs] = '\0'; puts(data); return; } // if we are done with all the characters of both string if (indx1==len1 || indx2==len2) return; // here we have to print all sub-sequences lexicographically, // that's why we start from 'a'to'z' if this character is // present in both of them then append it in data[] and same // remaining part for (char ch='a'; ch<='z'; ch++) { // done is a flag to tell that we have printed all the // subsequences corresponding to current character bool done = false; for (int i=indx1; i<len1; i++) { // if character ch is present in str1 then check if // it is present in str2 if (ch==str1[i]) { for (int j=indx2; j<len2; j++) { // if ch is present in both of them and // remaining length is equal to remaining // lcs length then add ch in sub-sequenece if (ch==str2[j] && lcs(str1, str2, len1, len2, i, j) == lcslen-currlcs) { data[currlcs] = ch; printAll(str1, str2, len1, len2, data, i+1, j+1, currlcs+1); done = true; break; } } } // If we found LCS beginning with current character. if (done) break; } }}// This function prints all LCS of str1 and str2// in lexicographic order.void prinlAllLCSSorted(string str1, string str2){ // Find lengths of both strings int len1 = str1.length(), len2 = str2.length(); // Find length of LCS memset(dp, -1, sizeof(dp)); lcslen = lcs(str1, str2, len1, len2, 0, 0); // Print all LCS using recursive backtracking // data[] is used to store individual LCS. char data[MAX]; printAll(str1, str2, len1, len2, data, 0, 0, 0);}static int arr[][];
static void lcs(String s1, String s2) {
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1))
arr[i][j] = arr[i - 1][j - 1] + 1;
else
arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
}
}
}
static Set<String> lcs(String s1, String s2, int len1, int len2) {
if (len1 == 0 || len2 == 0) {
Set<String> set = new HashSet<String>();
set.add("");
return set;
}
if (s1.charAt(len1 - 1) == s2.charAt(len2 - 1)) {
Set<String> set = lcs(s1, s2, len1 - 1, len2 - 1);
Set<String> set1 = new HashSet<>();
for (String temp : set) {
temp = temp + s1.charAt(len1 - 1);
set1.add(temp);
}
return set1;
} else {
Set<String> set = new HashSet<>();
Set<String> set1 = new HashSet<>();
if (arr[len1 - 1][len2] >= arr[len1][len2 - 1]) {
set = lcs(s1, s2, len1 - 1, len2);
}
if (arr[len1][len2 - 1] >= arr[len1 - 1][len2]) {
set1 = lcs(s1, s2, len1, len2 - 1);
}
for (String temp : set) {
set1.add(temp);
}
//System.out.println("In lcs" + set1);
return set1;
}
}
lcs(s1, s2);
System.out.println(lcs(s1, s2, s1.length(), s2.length()));When you calculate a cell in the DP table, keep a backpointer to the previous cell used for that result. If there is a tie, keep multiple backpointers for all of the tied results. Then retrace the path using the backpointers, following all paths.I can even do this without keeping an extra backpointer. I can use the precalculated DP table to do so. But the problem(to me) occurs when there is a tie
LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs( char[] X, char[] Y, int m, int n ) { int L[][] = new int[m+1][n+1]; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ 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]; } /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs( char[] X, char[] Y, int m, int n ) { if (m == 0 || n == 0) return 0; if (X[m-1] == Y[n-1]) return 1 + lcs(X, Y, m-1, n-1); else return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); }