Medium Divide and Conquer > Dynamic Programming

There were three friends in a university. Their names were Atik, Alomgir and Bappa. They used to eat, hang around and play all together. They were three top most students in their class and they used to understand programming very well and knew how to solve problems although they were not so good at programming. Once their sir came in the class and said ,Today i won't teach you anything, rather i will ask you a question. If anyone of you can answer that question. He will be given a very special prize. You three will be given three names of three places. You will have to find maximum common subsequence (MCS) among three names. If there are one more maximum subsequence then you will have to find lexicographically smallest MCS. Example : First place: abc Second place: bcd Third place: cde Atik ans : 2 bc ( not correct) Bappa ans: 3 abc (not correct) Alonggir ans :1 c (correct ) As if Alomgir gave the correct answer so he got that special prize. So, The same problem is given for you today, the boy among you could solve the problem he will be given the problem setter special prize. Input: ------ Input starts with an integer T (≤ 200), denoting the number of test cases.The next three lines will contain names of three places of length 1 to 50. And the string will contain alphanumeric characters only(a-z , A-Z ) and must be 'A' and 'a' difference . Output: ------- For each case, print one line containing the case number, length of MCS and the lexicographically smallest MCS . If the MCS length is 0 then just print '**T.A.T'** Sample Input ------------ 2 Aab HHH KKKK zxcvbn hjgasbznxbzmx HHzxbBb Sample Output ------------- Case 1: 0 T.A.T Case 2: 3 zxb

Anowar Hossain Anu