# What is 'longest common subsequence'?

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

## 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 on other sites
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 on other sites
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"

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 on other sites
Quote:
 Original post by Anonymous PosterA 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 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 on other sites
A subsequence allows you to skip some sequence elements (here letters), but you can still only go forward.

##### Share on other sites
Quote:
 Original post by ph33rSo 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

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633709
• Total Posts
3013478
×