Longest Common Subsequence Question

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?

Comment on Longest Common Subsequence Question

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` [download] 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` [download]	[reply] [d/l] [select]
Re^2: Longest Common Subsequence Question by Anonymous Monk on Nov 19, 2007 at 04:11 UTC
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?	[reply]
Re^3: Longest Common Subsequence Question by ikegami (Patriarch) on Nov 19, 2007 at 04:20 UTC
Oops, I meant `S1 = aa1bbb S2 = aa2bbb S3 = aa` [download]	[reply] [d/l]
Re^4: Longest Common Subsequence Question by Anonymous Monk on Nov 19, 2007 at 04:35 UTC
Re^5: Longest Common Subsequence Question by ikegami (Patriarch) on Nov 19, 2007 at 04:41 UTC
Some notes below your chosen depth have not been shown here
Re^4: Longest Common Subsequence Question by Anonymous Monk on Nov 20, 2007 at 01:25 UTC
Re: Longest Common Subsequence Question by Limbic~Region (Chancellor) on Nov 20, 2007 at 00:35 UTC
Anonymous Monk, Yes, it will fail. You may have been thinking of my Challenge: Hidden Message and my follow up Longest Common Subsequence. In particular, pay attention to this which implements your suggestion but fails to find the correct answer. Cheers - L~R	[reply]


Perl-Sensitive Sunglasses
	PerlMonks