Solve a problem – Filter by language, license, keyword, owner, or search text to find code & info fast.

# 'A' Longest Common Subsequence (LCS) implementation

Unmodified
Removed
• ## Content

r20 r21
5858
5959or ``S={A,C,G,Z}`` for our first potential "longish" subsequence.
6060
6161Then 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`.
6262
63 The algorithm I came up with is implemented in ``:snippet:`379```.
63The algorithm I came up with is implemented in :snippet:`379`.
6464
6565Now, 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.
6666
6767What 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```.
6868