Sign in to follow this  

What is 'longest common subsequence'?

This topic is 4810 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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]

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
A subsequence is not the same as a substring.
My bad. My brain was frozen.

@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.

Share this post


Link to post
Share on other sites
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 ?

Share this post


Link to post
Share on other sites
Quote:
Original post by ph33r
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 ?
I believe it would actually be ACDEG, since E appears between D and G in both. F could be used instead of E

Share this post


Link to post
Share on other sites

This topic is 4810 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this