Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Longest Common Subsequence Question

by Anonymous Monk
on Nov 19, 2007 at 03:46 UTC ( [id://651576]=perlquestion: print w/replies, xml ) Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Dear monks,

I saw a Perl implementation on this forum to determine the longest common subsequence among M strings. Let assume there are three strings S1, S2, and S3. Would the common subsequence be found by determining the common subsequence between S1 and S2 (let's call it R12), then take this result and find the common subsequence between it (R12) and S3. Will this work or under what condition will this method fail? Any thought?

Replies are listed 'Best First'.
Re: Longest Common Subsequence Question
by ikegami (Patriarch) on Nov 19, 2007 at 03:57 UTC

    Your method would fail for

    S1 = aabbb S2 = aabbb S3 = aa

    The answer is "aa", but your method will try to find the LCS("bbb", "aa") and will fail to find a result.

    Update: Oops, I meant

    S1 = aa1bbb S2 = aa2bbb S3 = aa
      I thought the longest common subsequence between S1 and S2 in this case is aabbb.
      And then the longest common subsequence between this result aabbb and S3 (aa) is aa. Am I missing something?

        Oops, I meant

        S1 = aa1bbb S2 = aa2bbb S3 = aa
Re: Longest Common Subsequence Question
by Limbic~Region (Chancellor) on Nov 20, 2007 at 00:35 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://651576]
Approved by GrandFather
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others examining the Monastery: (3)
As of 2024-10-06 10:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    The PerlMonks site front end has:





    Results (43 votes). Check out past polls.

    Notices?
    erzuuli‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.