For this dynamic programming problem and the next one, be sure to

(a) describe the subproblem

(b) give a recurrence for the subproblem

(c) provide pseudo-code showing how a table for the subproblems is filled

(d) give the time and space requirements of your method Suppose we have two transmitters, each of which sends out repetitions of some short string.

For example, transmitter 1 may repeat string x=101 over and over, so what we will hear from it will be a prefix of x k - that is, x concatenated to itself k times, possibly with a few bits chopped of the end (as in 10110110). Transmitter 2 repeats another string, y. Our job is to determine if a sequence s that we have heard is an interleaving of these two transmissions.

For example, suppose transmitter 1 repeats x=101 and transmitter 2 repeats y=01. The sequence 010111010101 can be unraveled into x and y: positions 1, 5, 9, and 12 contain 0101, a repetition of y, while the remainder of the string contains 10110110, a repetition of x.

Describe an efficient algorithm which takes a sequence s of length n, and two strings x and y, and determines if s is an interleaving of repetitions of x and y.