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.
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