Define a merge of two strings to be any string formed from all the characters in both strings, interspersed, but in their original order. For example, for the strings chocolate and chips, cchocholaiptes is a merge, but chocochilatspe or bananasplit are not. This problem requires writing a program that can tell if a given string is a merge of two other given strings. For the purposes of this problem, the input strings will contain only lowercase alphabetic characters.
The input file consists of sets of three strings A, B, and C, in that order, one string per line. The file contains no blank lines. The strings A and B will not exceed 1000 characters, and C will not exceed 2000 characters.
For each set of 3 input lines, if C (the third) is not a merge of A and B (the first and second), write a single line to the output file that reads "*** NOT A MERGE ***". If C is a merge, write to the output file the string C rewritten with the characters from A in uppercase. If more than one merge is possible, string C should be wriften with each character of A occurring as early as possible (examine the sample input/output below for such examples).
chocolate chips cchocholaiptes chocolate chips bananasplit abac bad ababacd
CcHOChOLAipTEs *** NOT A MERGE *** ABAbaCd