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
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
However, if we are asked to return all LCS's, then we need to modify the way we build the second matrix and backtracking algorithm. There are three cases to be considered while building the second matrix.
1. If characters at positions i, j are same, then we place a diagonal arrow at position [i][j].
2. If characters are not same, then we compare values at positions [i-1][j] and [i][j-1] in the first matrix. If value at [i-1][j] is greater than [i][j-1] then we place a left arrow otherwise an upward arrow.
3. In LCS algorithm, if both values are equal, then either an upward arrow or a left arrow is placed depending on the implementation. This basically defines the direction that is taken while backtracking in LCS.
If we want to find out all LCS's, then in the third step, we have to place a new character and while back tracking, we have to go in both upward and left directions when ever we come across this character. This little modification should be enough to find out all LCS's.
Read full article from All Longest Common Subsequences | nikhilnayunigari
No comments:
Post a Comment