Re: Longest Common Subsequence Question

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]

Comment on Re: Longest Common Subsequence Question Select or Download Code

Replies are listed 'Best First'.
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
with S1=aa1bbb and S2=aa2bbb the longest common subsequence between them still would be aabbb and the longest common subsequence between aabbb and aa would still be aa. This is the longest common subsequence, not the longest common substring.	[reply]
Re^5: Longest Common Subsequence Question by ikegami (Patriarch) on Nov 19, 2007 at 04:41 UTC
Re^6: Longest Common Subsequence Question (no) by tye (Sage) on Nov 19, 2007 at 05:49 UTC
Re^6: Longest Common Subsequence Question by sgt (Deacon) on Nov 19, 2007 at 14:06 UTC
Re^4: Longest Common Subsequence Question by Anonymous Monk on Nov 20, 2007 at 01:25 UTC
Thank you all. This one got me thinking for awhile there.	[reply]