Longest Common Subsequence

This is a discussion on Longest Common Subsequence within the Tech Board forums, part of the Community Boards category; Hi everyone! I'd like to know how to compute the length of an LCS (Longest Common Subsequence). I have the ...

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    81

    Longest Common Subsequence

    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!!
    "Our greatest glory consists not in never failing,
    but in rising every time we fall."

    Oliver Goldsmith (1730-1774).
    Anglo-Irish writer, poet and playwright.

  2. #2
    PC Fixer-Upper Waldo2k2's Avatar
    Join Date
    May 2002
    Posts
    2,001
    PHP and XML
    Let's talk about SAX

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    81
    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:

    Code:
    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.
    Last edited by stimpyzu; 04-04-2005 at 01:37 PM.
    "Our greatest glory consists not in never failing,
    but in rising every time we fall."

    Oliver Goldsmith (1730-1774).
    Anglo-Irish writer, poet and playwright.

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    "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.

  5. #5
    Registered User
    Join Date
    Apr 2002
    Posts
    81
    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!
    "Our greatest glory consists not in never failing,
    but in rising every time we fall."

    Oliver Goldsmith (1730-1774).
    Anglo-Irish writer, poet and playwright.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. longest prefix
    By Marksman in forum C Programming
    Replies: 1
    Last Post: 03-14-2009, 11:19 PM
  2. How to handle multiple cases which use common code?
    By tmaxx in forum C Programming
    Replies: 3
    Last Post: 10-03-2008, 07:42 AM
  3. longest common substring problem
    By Enchanter88 in forum C++ Programming
    Replies: 4
    Last Post: 09-29-2007, 11:02 AM
  4. longest common substring
    By TechHigh in forum C Programming
    Replies: 6
    Last Post: 01-05-2007, 02:18 AM
  5. Lowest Common Factor
    By PJYelton in forum C++ Programming
    Replies: 9
    Last Post: 12-23-2002, 08:30 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21