LCS problem: Suppose we are given two strings x[1 . . . n] and y[1 . . . m]. A substring from x (for example) of length k, is a string of the type x[i1]x[i2] . . . x[ik] where the indices involved i1, i2, . . . , ik satisfy 1 <= i1 < i2 < . . . < ik <= n. Show how you will solve using Dynamic Programming the problem of finding the longest common substring of x and y - so a substring both of x, y and the longest such candidate substring. Hint: Either (a) the last character of x, y are both involved in the longest common substring - when can this happen and if this is so, the LCS except its last character is LCS of what other strings? If not (a) then (b) what happens if the last character of x is not involved, or (c) the last character of y is not involved, or (d) last characters of x, y are not involved. Give the recurrence in detail. Then describe how to proceed from here (storage structure, traversal order etc.) and estimated run-time. You do not need to write pseudo-code for this. 6