Solve a problem – Filter by language, license, keyword, owner, or search text to find code & info fast.

# 'A' Longest Common Subsequence (LCS) implementation

Unmodified
Removed
• ## Content

r12 r13
6060
6161Then we move to starting at :math:`x_2` and do it all again form :math:`y_1` which immediately match.  We proceed to :math:`x_3` and that also matches :math:`y_2`.  Then to :math:`x_4` which matches :math:`y_4`.
6262
6363The algorithm I came up with is implemented in ``:snippet:`379```.
6464
65 Now, to understand the potential cost of this it is clear that we go through Y at least n times (where n is the number of items in X).  So that is O(n*m) (m is the number of items in Y).  However, at each point we do not match, we could potentially rewind multiple times.  Doing a lot of testing with no with sequences like X={A,B,C,D} and Y={D} I saw some extra looping which I stopped with some if statements but these cost time.  In any case, what you see is the final one and it still will cost more comparisons than the next one.
65Now, to understand the potential cost of this it is clear that we go through Y at least n times (where n is the number of items in X).  So that is O(n*m) (m is the number of items in Y).  However, at each point we do not match, we could potentially rewind multiple times.  Doing a lot of testing with no with sequences like X={A,B,C,D} and Y={D} I saw some extra looping which I stopped with some if statements but these cost time.  In any case, what you see is the final version and it still will cost more comparisons than the ideal LCS algorithm.
6666
67 What if we take every subsequence of X and look for it in Y?  Then we have the longest subsequence, X itself, then start knocking off one character at a time and check again.  This truly brute force algorithm is provided in ``:snippet:`380```
67What if we take every subsequence of X and look for it in Y?  Then we have the longest subsequence, X itself, then start knocking off one character at a time and check again.  This truly brute force algorithm is provided in ``:snippet:`380```.
68
69A critical insight into this problem is to realize that it can be broken down into sub-problems.  Let us define a suffix as the first part of a sequence.  For example, above suffixes would be A, AB, ABC, ABCD & etc.
70
71Now, suppose two sequences start with the same element. Then to find their LCS we need to only compare the remainder.  In other words, if the first item matches then a LCS is the item that matched plus a LCS of X = {:math:`x_2, x_3, .., x_i, .., x_n`} with Y = {:math:`y_2, y_3, .., y_j, .., y_m`}.
72
73If the first element does not match, then obviously it is not part of an LCS and can be ignored.  But then how do we proceed?  We must check X = {:math:`x_2, x_3, .., x_i, .., x_n`} against the Y = {:math:`y_3, y_4, .., y_j, .., y_m`} and vice-versa to see which comparison yields a longer LCS.
74
75This solution is analogous to the description in the `Wikipedia`_ reference except that there it is more formally defined and he is removing the last element instead of the first.
76
77My version leads to a recursive solution like ``:snippet:`381```.
6878
6979
7080Chapter 2 Implementation
7181------------------------
7282
73 The code I implemented uses memoization from the `UCI`_ article and the printDiff method is basically a reverse version of the back-tracking printDiff algorithm of the `Wikipedia`_ article
83I went through a series of implementations for fun and exploration.  The first and most basic was a C version for char* comparisons.  The second was a C++ version which used memoization to keep track of the comparisons
7484
7585Section 2.1 C version for char*
7686*******************************
7787
78 First, I just pushed through the implementation.  It probably has bugs.  I've revisited it a few times but basically only to look at it for the NEXT implementation.  It can be found in whole at the snippet ``:snippet:`374```.
88The first code I implemented was to demonstrate the memoization algorithm from the `UCI`_ article pretty much as-is (``:snippet:374```). It is implemented in C.
7989
8090Section 2.2 C++ version (first try)
8191***********************************
8292
83 The next thing I decided to do was think about this in terms of the sequence being any object.  As a result I would need to think more about indices and what it meant to be at the end of a set of objects and the size of the object collection.  That was too much to think about so I decided to make an LCS C++ template class that could be used for c++ containers or at least some containers. I'm still working on it here: ``:snippet:`375```
93The next thing I decided to do was think about this in terms of the sequence being any object.  As a result I would need to think more about indices and what it meant to be at the end of a set of objects and the size of the object collection.  That was too much to think about so I decided to make an LCS C++ template class that could be used for c++ containers or at least some containers. The code is here ``:snippet:`375``` and test/example code is here ``:snippet:`382```.
8494
85 Chapter 3 More to do
95
96
97Chapter 3  What else?
8698---------------------