Assume X and Y are given strings, with |X| = |Y | = n, and assume that |LCS(X, Y )| n10 (that is, all but at most 10 characters match). Suggest an O(n) time algorithm for finding LCS(X, Y ).

Extend your answer in the following way: Assume a parameter k < n is given. Show how you could find in time O(kn) whether |LCS(X, Y )| n k. Show how this could be used for computing LCS(X, Y ) in time O(nk), where k = n |LCS(X, Y )|. Hint: Assume that the matrix c[1..n, 1..n] is given when all cells are initialized to zero, so you do not need to spend any time initializing them. Show that only O(nk) cells need to be visited.