All Longest Common Subsequences | nikhilnayunigari
Most of us are aware of the dynamic programming problem Longest Common Subsequences. Given two strings, it returns a longest common sequence. Even though there are multiple sequences of same length, we can only get one using the LCS algorithm.
The above problem "Trip" asks to print all longest common sequences in lexicographic order. This can be done by modifying the original algorithm.
The original LCS algorithm has two parts. In the first part, we build two matrices. The first matrix gives us the length of the LCS and the second matrix gives us directions to follow while backtracking. In the second part we use directions in the second matrix and build LCS. A detailed explanation of this algorithm can be found at
Read full article from All Longest Common Subsequences | nikhilnayunigari
No comments:
Post a Comment