You're consulting for a group of people (who would prefer not to be mentioned here by name) whose jobs consist of monitoring and analyzing electronic signals coming from ships in coastal Atlantic waters. They want a fast algorithm for a basic primitive that arises frequently:" untangling" a superposition of two known signals. Specifically, they are picturing a situation in which each of two ships emit a short sequence of Os and Is over and over, and they want to make sure that the signal they are hearing is simply an interleaving of these two emissions, with nothing extra added in. This describes the whole problem; we can make it a little more explicit as follows. Given a string x consisting of 0s and 1s, we write x^k to denote k copies of x concatenated together. We say that a string x' is a repetition of x if it is a prefix of x^k for some number k. So x' = 10110110110 is a repetition of x = 101
We say that a string s is an interleaving of x and y if its symbols can be partitioned into two (not necessarily contiguous) subsequences s' and s", so that s' is a repetition of x and s" is a repetition of y. (So each symbol in s must belong to exactly one of s' or s".) For example, if x = 101 and y = 00. then s = 100010101 is an interleaving of x and y. since characters 1.2, 5, 7, 8.9 form 101101-a repetition of x-and the remaining characters 3, 4.6 form 000-a repetition of y
In terms of our application, x and y are the repeating sequences from the two ships, and s is the signal were listening to: We want to make sure s "unravels" into simple repetitions of x and y.
Part A Give a recurrence relation of the problem.
Part B Design an efficient algorithm that takes strings s, x, and y and decides if s is an interleaving of x and y.