Problem 3: You're consulting for a group of people (who would prefer not to be men- tioned here by name) whose jobs consist of monitoring and analyzing electronic signals coming from ship s in coastal Atlantic waters. They want a fast algorithm for a ba ic prive that arises frequently: "untangling" a superposition of two known signals. Specifically, they're picturing a situation in which each of two ships is emitting a short sequence of 0's and 1's over and over, and they want to make sure that the signal they're hearing is simply an interleaving of these two emissions, with nothing extra added in Given a string z consisting of O's and 1's, we write *to denote k copies of a con- catenated together. We say that a string is a repetition of z if it is a prefix of for soine number k. So x'-101 10110110 is a repetition of z-101 We say that a string s is an interleaving of r and y if its symbols can be partitioned into two (not necessarily contiguous) subsequences s' and s", so that s is a repetition of r and s" is a repetition of y. ?So each symbol in s must belong to exactly one of 8, or s") For example, if 2, 101 and y 00, then 8-1000101010 is an interleaving of and y since characters 1,2,5,7,8,9 form 10110-a repetition of r-and the remaining characters 3,4,6,10 form 0000-a repeton of y In terms of our application and y are the repeating sequences from the two ships and s is the signal wer listening to We want to make su "untangles into simple repetitions of and y A) Give recurrence relation of the problem B) Design an efficient algorithm that takes strings s, , and y and decides if s is an interleaving of and y