Longest common subsequence of three strings.

We are given three strings a = (a1, a2, . . . , a_l), b = (b1, b2. . . . , b_m), and c = (c1, c2, . . . , c_n). Find the maximum length of a common subsequence of a, b, and c (i.e., the number of characters in a longest string that is the substring of a, b and c).

We define subproblems as follows. For i = 0, . . . , l`, j = 0, . . . , m, and k = 0, . . . , n, let OPT(i, j, k) denote the maximum length of a subsequence of the three strings (a₁, . . . , a_i), (b₁, . . . , b_j ), and c(1, . . . , k). Then the original problem is to find OPT(l, m, n). Note that if any of the words has zero letters, then any common subsequence has 0 length. Consequently, OPT(0, j, k) = 0, OPT(i, 0, k) = 0, and OPT(i, j, 0) = 0 for all i, j, k.

(a) Find a recurrence relation for OPT(i, j, k), i, j, k 1; justify your answer.

(b) Provide pseudocode for a DP algorithm that returns OPT(l, m, n).