Free your code from a slow death on your hard drive

# 'A' Longest Common Subsequence (LCS) implementation

Unmodified
Added
Removed
• ## Content

r9 r10
3939Which gives ``S={B,C,D,G,Z}``
4040
4141Chapter 1 Logic/Algorithm
4242-------------------------
4343
44 At first analysis, if we have two sequences for which we are seeking a longest common subsequence we can view find the solution in the following way.  We break it down and do it by brute force.  If :math:`x_1` matches :math:`y_1` then we move on to the next.  If not, we compare :math:`x_1` with :math:`y_2`.  We move on to the next :math:`x_i` when we either match it to a :math:`y_j` or we get to the end.  Then we move on to :math:`x_2` and compare it starting from the point past where we found the match in Y until we reach the end of both.  Then we start at :math:`x_2` and do it all over again.  For each :math:`x_i` we traverse all :math:`y_j`, each time we could end up with a new subsequence.
44At first analysis, if we have two sequences for which we are seeking a longest common subsequence we can find the solution in the following way.  This is the brute force method.  If :math:`x_1` matches :math:`y_1` then we move on to the next.  If not, we compare :math:`x_1` with :math:`y_2`.  We keep proceeding through Y comparing to :math:`x_1` until we find a match, for my example above, at :math:`y_3`, or we get to the end of Y.
45
46When we get to the match point, we increment the X position and proceed from where we were in Y.  Using the example above, we found :math:`y_3` == :math:`x_1` so we go to :math:`x_2` and start comparing with :math:`y_4`.  This time we will get to the end of Y in our example.
47
48If we get to the end of Y without a match then we move on to the next X, :math:`x_2` in our example, and reset the comparison to the last place that we found a match in Y + 1, which in this case was :math:`y_3` and go to the next one, :math:`y_4`.
49
50In our example we will once again hit the end of Y without a match; this time we move to :math:`x_3`. Here we find a match because :math:`y_5` == :math:`x_3` == 'C'.
51
52We increment our position in both sequences to :math:`x_4` and :math:`y_6`.  Proceeding as before we should reach :math:`x_7` matching :math:`y_6` and :math:`x_8` matching :math:`y_7`.
53
54At that point, both increment to the end without any more matches and we have found::
55
56     A   B C   D B A     G Z C D C A
57 B C A D   C             G Z
58
59or ``S={A,C,G,Z}`` for our first potential "longish" subsequence.
60
61Then 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`.
62
63The algorithm I came up with is implemented here
4564
4665
4766Chapter 2 Implementation
4867------------------------
4968