A DNA sequence is a string consisting of only the characters G, C, T, and A. Suppose you're given two different DNA sequences, X (of length n) and Y (of length m), and you want to determine how many times string X appears as a substring of Y (the characters of X don't have to appear consecutively in Y, but they do have to appear in the same order as in X). Give an efficient algorithm that takes X and Y as inputs and outputs the number of times X appears as a substring of Y.

please define any subproblems (example: C(i,j) is the cost of multiplying matrices Ai...Aj) you are using, state the Recurrence for the entries including all base cases (and explain why it's a correct recurrence relation), give the pseudocode for the alg, and analyze its Running time.