A subsequence is a sequence that can be derived from another sequence by deletin

Question

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements; e.g. “acef” is a subsequence of “abcdef.” Consider the problem of finding the longest common subsequence of two sequences – this is a task versioning systems like git or cvs often solve. Show that this is a special case of the sequence alignment problem. Then, give a polynomial-time algorithm for finding the longest subsequence common to three sequences. Analyze its running time and argue why it is correct.

Explanation / Answer

Here it goes,

Let ss[i, j, k] is the longest common subsequence of prefixes A[1..i], B[1..j], C[1..k]

And We have:

ss[i, j, k] = ss[i - 1, j - 1, k - 1] + 1 if A[i] = B[j] = C[k]
max(ss[i - 1, j, k], ss[i, j - 1, k], ss[i, j, k - 1]) otherwise

Complexity:
O(len A * len B * len C)

note:
ss[i,j,k] = 0 if i == 0 or j == 0 or k == 0

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.