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

Explain yourself with reStructured Text, embedded code, graphs, charts, and LaTeX–style math. Join Siafoo Now or Learn More

'A' Longest Common Subsequence (LCS) implementation

Revision 10 vs. Revision 11

r10	r11
58	58
59	59	or ``S={A,C,G,Z}`` for our first potential "longish" subsequence.
60	60
61	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	62
63		The algorithm I came up with is implemented here
	63	The algorithm I came up with is implemented in ``:snippet:`379```.
	64
	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.
	66
	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.
64	68
65	69
66	70	Chapter 2 Implementation
67	71	------------------------
68	72