You are given two strings.Now you have to print all longest common sub-sequences in lexicographical order?
Input : str1 = "abcabcaa", str2 = "acbacba" Output: ababa abaca abcba acaba acaca acbaa acbca
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.
Below is the implementation of algorithm.