Longest Common Subsequence

[stimpyzu]

Hi everyone!

I'd like to know how to compute the length of an LCS (Longest Common Subsequence). I have the LCS-LENGTH(X,Y) code and it works fine, but I want to know how to fill a table by hand, i.e. inserting the length numbers and the arrows. I know some will tell me to follow the code but I can't understand how it works exactly. I need it to be explained to me in plain English. I can be a little dense at times!

Thanks for any help in advance!!

[Waldo2k2]

http://www.google.com/search?q=longe...on+subsequence

please, no homework questions

[stimpyzu]

I had already looked at all those links that Google search gave for
LCS already (as well as for dynamic programming, etc, etc.) and I
had went through all my books AND I even looked at the C Boards
Tutorials. I usually don't post a question before having done an
extensive search on my own first. Those Google links didn't help me
by the way.

It is clearly stated in the homework policy:

The purpose of these board is not for other people to do your 
homework for you. Try things out work on your own, homework has 
a purpose. If you still have trouble with a specific piece of code or 
concept please feel free to ask. But please do not ask people to do 
your entire homework for you, it simply annoys people most of the 
time.

This does not say "Please no homework questions"!


I was asking for help, to be pointed in the right direction, not for
anyone to do my work. If I was asking for my work to be done for
me, I would have provided the sequence of numbers that needed to
be put in the table.

I thought this board was to help people, not to be rude and
condescending to them.

[Perspective]

"I'd like to know how to compute the length of an LCS "


This is asking someone to solve the entire problem for you. If you post specific questions as to what parts of this problem are giving you trouble your more likely to get a usefull response.

[stimpyzu]

Are you kidding me? What problem is there to solve for me? I didn't provide the numbers!

I was kindly asking for someone to explain the mechanics of it! How do you compute the length of an LCS?

The part that is giving me trouble is how do I fill the table by hand?

For example

00000
01122
01233
01233

I get that you get a 1 or a 2 or a 3 because you've "hit" a common number or letter in your sequence. But I don't get exactly how to fill in the table and why the arrows point where they point (except for the diagonal arrows) Is this more specific?

And this is just an "imaginary" table with no input X and Y. Specifically because I don't want to ask anyone to solve the problem for me! I need to know how to solve it myself or else I'm screwed. I just wanted some help in figuring it out! What a helpful board! Geez!