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

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

'A' Longest Common Subsequence (LCS) implementation

Revision 11 vs. Revision 12

r11	r12
62	62
63	63	The algorithm I came up with is implemented in ``:snippet:`379```.
64	64
65	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	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.
	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```
68	68
69	69
70	70	Chapter 2 Implementation
71	71	------------------------
72	72