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.