1. Two character strings may have many common substrings. For example, photograph and tomography have several common substrings of length 1 (i.e., single letters), and common substrings ph, to, and ograph (as well as all the substrings of ograph). The maximum common substring length in this case is 6. Let X = x1x2...xn and Y = y1y2...ym be two character strings. The Maximum Common Substring (MCS) Problem is to find the maximum common substring length for X and Y.

Let s[i, j] = the length of the longest common substring ending at xi and yj. A recursive function to find the value of s[i, j] is: s[i - 1, j - 1] + 1 if xi = yj 0 otherwise. Give a dynamic programming algorithm to solve this problem. What is its time complexity?