Problem
You are consulting for a group of people (who would prefer not to be mentioned here by name) whose job consists of monitoring and analyzing electronic signals coming from ships in the Atlantic ocean. 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 is emitting a short sequence of 0s and 1s over and over, and they want to make sure that the signal they are hearing is simply an interweaving of these two emissions, with nothing extra added in. The short sequence emitted by each ship is known to the ship and to you, the receiver.
Given a string x consisting of 0s and 1s, we write xk to denote k copies of x concatenated together. We say that string x′ is a repetition of x if it is a prefix of xk for some number k. So, x′ = 10110110110 is a repetition of x = 101.
We say that a string s is an interweaving of x and y if its symbols can be partitioned into two (not necessarily contiguous) subsequence s′ and s′′ so that s′ is a repetition of x and s′′ is a repetition of y. Each symbol insmustbelongtoexactlyoneofs′ ofs′′. Forexample,ifx=101andy=0,thens=100010101isan interweaving of x and y since characters 1,2,5,7,8, and 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 we are receiving. We want to make sure s "unravels" into simple repetitions of x and y.
You want a "fast algorithm for ...'untangling' a superposition of two known signals", x and y. You receive some set of symbols s. You do not know if the signal you receive has its first symbol in x, y, or a symbol that is extra and added in. You need to use your knowledge of x and y and the received signal s to determine if s consists only of valid interwoven symbols from x and y. That may require your solution to discard some symbols at the beginning or end of s to get to at least a full match of x and a full match of y. The received signal could be too short to do this. If you can't determine that the signal is an interweaving of x and y, either because s is not long enough to do so or because s contains symbols not in x or y then you cannot decide that s is an interweaving of x and y.
• Give an efficient algorithm that takes strings s, x, and y and decides if s is an interweaving of x and y. Derive the computational complexity of your algorithm. Do not copy the answer from other online resource, I will give you negative feedback for copy other answer.