LCS for 3 strings - proof

Question

Can we extend LCS algorithm for two strings from the document below to three strings in this way?

http://www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdf - document, page 5 point 2.

1. If xm != yn or xm != tj then zk != xm implies that Z is an LCS of Xm-1 and Y and T.

"If zk != xm, then Z is a common subsequence of Xm−1 and Y and T. If there were a common subsequence W of Xm − 1 and Y and T with length greater than k , then W would also be a common subsequence of X m and Y and T , contradicting the assumption that Z is an LCS of X and Y and T."

where T = is our third string

Answer 1

A good way to think about this is with dynamic programming arrays. For 2 strings, you have a dynamic programming matrix of size M x N if your strings are length M and N. For 3 strings, you have a 3-dimensional dynamic programming array of size L x M x N if your strings are length L, M, N. At each entry (i,j,k) of the dynamic array, you store the length of the LCS between the prefixes of the 3 strings that have lengths i,j,k. It is easy to see how to compute entry (i,j,k) in the array if you know the solutions for entries (i-1,j,k), (i,j-1,k), (i,j,k-1), and (i-1,j-1,k-1). Basically the predecessor (i-1,j-1,k-1) gets its entry incremented by 1 before propagating to (i,j,k) if positions i,j and k in the strings match, and all other entries are propagated to (i,j,k) without incrementing. Then you take the max of the propagated entries. This looks like what your quote is trying to say, but an easy way to see the dynamic programming recursion is to just imagine how you would compute (i,j,k) in the array if you knew all the aforementioned predecessors. Thus you can fill in the array starting with the first column with indices (1,1,k) in increasing order of k, and then fill in for (1,j,k) in increasing order of j (in increasing order of k), and then fill in the array for (i,j,k) in increasing order of i (in increasing order of j) (in increasing order of k)).