Hi!! I need help with this problem please.. This is an Algorithm problem.. I don't need the code for it, just give the answer, analyze and explain it... Finally, please don't look up the algorithm online . TIA

Suppose that you have two strings, Si, S2, each consisting of characters from some small alphabet. The lengths of the strings are k and n respectively. You can assume that n 2 k but not that k is necessarily some small value If we alternate reading characters from one string and then the other, we create a "blend" of the two strings. For example if S1 = DYNOGRASOAMA and S2- AMICPRMMINGISZING we can create this blend DYNAMICPROGRAMMINGISSOAMAZING Note that the length of a blend is n+k, and there can be many blends Now for the problem: Given three strings S1, S2 and C, determine if C is a blend of Si and S2. If Si and S2 have size k and n respectively, the time complexity should be O(kn) You should address the following in your answer: Formulate the problem recursively, including an informal justification for its correct- ness. (How can you categorize subproblems that will be helpful to solve first?) How many distinct subproblems are there? Mention what you consider to be a base case What is the size of the dynamic programming table that you will use, how do you fill it in, and where are the base cases and final answer located? Suppose that you have two strings, Si, S2, each consisting of characters from some small alphabet. The lengths of the strings are k and n respectively. You can assume that n 2 k but not that k is necessarily some small value If we alternate reading characters from one string and then the other, we create a "blend" of the two strings. For example if S1 = DYNOGRASOAMA and S2- AMICPRMMINGISZING we can create this blend DYNAMICPROGRAMMINGISSOAMAZING Note that the length of a blend is n+k, and there can be many blends Now for the problem: Given three strings S1, S2 and C, determine if C is a blend of Si and S2. If Si and S2 have size k and n respectively, the time complexity should be O(kn) You should address the following in your answer: Formulate the problem recursively, including an informal justification for its correct- ness. (How can you categorize subproblems that will be helpful to solve first?) How many distinct subproblems are there? Mention what you consider to be a base case What is the size of the dynamic programming table that you will use, how do you fill it in, and where are the base cases and final answer located