The longest common subsequence problem is as follows: Given two sequences A = a1, a2, . . . , aM, and B = b1, b2, . . . , bN, find the length, k, of the longest sequence C = c1, c2, . . . , ck such that C is a subsequence (not necessarily continguous) of both A and B. As an example, if
A = d,y,n,a,m,i,c
and
B = p,r,o,g,r,a,m,m,i,n,g,
then the longest common subsequence is a,m,i and has length 3. Give an algorithm to solve the longest common subsequence problem. Your algorithm should run in O(MN) time.