Browse › Articles › 'A' Longest Common Subsequence (LCS) implementation › History › Revision 9 vs. Revision 10

Free your code from a slow death on your hard drive Join Siafoo Now or Learn More

'A' Longest Common Subsequence (LCS) implementation

Revision 9 vs. Revision 10

Legend:

: Unmodified
: Added
: Removed

Content

r9	r10
39	39	Which gives ``S={B,C,D,G,Z}``
40	40
41	41	Chapter 1 Logic/Algorithm
42	42	-------------------------
43	43
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.
	44	At 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
	46	When 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
	48	If 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
	50	In 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
	52	We 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
	54	At 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
	59	or ``S={A,C,G,Z}`` for our first potential "longish" subsequence.
	60
	61	Then 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
	63	The algorithm I came up with is implemented here
45	64
46	65
47	66	Chapter 2 Implementation
48	67	------------------------
49	68

Login
Password
	Remember me