Jump to content
  • Advertisement
Sign in to follow this  
ph33r

What is 'longest common subsequence'?

This topic is 5005 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
Advertisement
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.

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
A subsequence allows you to skip some sequence elements (here letters), but you can still only go forward.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!