## Sunday, November 13, 2016

### Print all longest common sub-sequences in lexicographical order - GeeksforGeeks

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 lcs`
`int` `lcslen = 0;`
`// dp matrix to store result of sub calls for lcs`
`int` `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 lcslen`
`void` `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);`
`}`
https://stackoverflow.com/questions/16848704/all-possible-lcslongest-common-subsequence-of-two-strings

``````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>();
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);
}
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) {
}
//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 ```
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
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));`
`  ``}`