What is 'longest common subsequence'?
Author
I'm reading through an article at topcoder.com about dynamic programming and they start off with a problem called the longest common subsequence.
" given the strings "ABCDE" and "DACACBE", the longest common subsequence is "ACE". "
I can't even begin to understand how they solved the problem because I don't understand what its asking for. I googled around and got thousands of links to some very mathematical definitions of what it is, but i still can't understand how they got ACE from those two strings.
Looks (to me) like a terrible, terrible typo might be the culprit. The Longest Common Subsequence is the longest subsequence (think substring) X that is equal for two "supersequences" A and B of X.
A subsequence is not the same as a substring. I'm bad at explaining things, so here's some examples of a subsequence from the sequence "ABCDEF"
ADF
ABF
ABCEF
CDF
EF
Here are some examples of sequences that are _not_ subsequences of "ABCDEF"
ACB
DEFA
FA
DB
Make sense? So you can construct a subsequence by throwing out some of the elements of the original sequence, but preserving the order. [partial definition from the interweb]
ADF
ABF
ABCEF
CDF
EF
Here are some examples of sequences that are _not_ subsequences of "ABCDEF"
ACB
DEFA
FA
DB
Make sense? So you can construct a subsequence by throwing out some of the elements of the original sequence, but preserving the order. [partial definition from the interweb]
Quote:Original post by Anonymous PosterMy bad. My brain was frozen.
A subsequence is not the same as a substring.
@ph33r:
"ACE" is a longest common subsequence. Using the AP's explanation, it should be obvious that "ABE" is another valid subsequence of equal length.
Man, I'm getting rusty.
Author
So a subsequence, would be just taking some letters out of a strng? As long as I don't change the order of the string's letters I will get a sub sequence?
So the LCS for "ABCDEFG" and "BACDFEG" would be ACDG ?
So the LCS for "ABCDEFG" and "BACDFEG" would be ACDG ?
A subsequence allows you to skip some sequence elements (here letters), but you can still only go forward.
Quote:Original post by ph33rI believe it would actually be ACDEG, since E appears between D and G in both. F could be used instead of E
So a subsequence, would be just taking some letters out of a strng? As long as I don't change the order of the string's letters I will get a sub sequence?
So the LCS for "ABCDEFG" and "BACDFEG" would be ACDG ?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
