Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re^6: Longest Common Subsequence Question (no)

by tye (Sage)
on Nov 19, 2007 at 05:49 UTC ( #651595=note: print w/replies, xml ) Need Help??

in reply to Re^5: Longest Common Subsequence Question
in thread Longest Common Subsequence Question

No, it wouldn't; it is just harder to come up with the counter example. The one that pops into my mind is due to the fact that an algorithm that claims to find "the longest common subsequence" will actually find "one of the maximal common subsequences" and you may have needed to find some other one:

axbc abxc a1b2c

If the first run picks "axc" then you are doomed. If you get lucky and it picks "abc", then you win.

But I strongly suspect that you don't even need to rely on that quirk. Indeed, I now see that it is easy to extend the above example:

axybc abxyc a1b2c

The solution is "abc" but you will first pick "axyc" and so won't include "b" in the final "answer".

- tye        

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://651595]
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others avoiding work at the Monastery: (9)
As of 2023-12-03 11:52 GMT
Find Nodes?
    Voting Booth?
    What's your preferred 'use VERSION' for new CPAN modules in 2023?

    Results (20 votes). Check out past polls.