Algorithm
Article
Library
Snippet
Blog
Group
Users
Forum
Legend:
- Unmodified
- Added
- Removed
-
Content
r20 r21 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 in ``:snippet:`379```.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 version and it still will cost more comparisons than the ideal LCS algorithm. 66 66 67 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