Suppose ‘A’ = “brute”, and ‘B’ = “groot” The shortest supersequence will be “bgruoote”. As shown below, it contains both ‘A’ and ‘B’ as subsequences. A A A A A b g r u o o t e B B B B B It can be proved that the length of supersequence for this input cannot be less than 8. So the output will be bgruoote.
The first line of the input contains a single integer ‘T’ representing the no. of test cases. The first line of each test case contains a single string ‘A’, denoting the first string described in the problem. The second line of each test case contains a single string, ‘B’, denoting the second string described in the problem.
For each test case, print the shortest string ‘S’, which contains ‘A’ and ‘B’ as its subsequences. Print a separate line for each test case.
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
1 ≤ T ≤ 100 1 ≤ |A|, |B| ≤ 1000 Both strings consist of only lowercase English letters. 1 ≤ Σ(|A|+|B|) ≤ 3000 Time limit: 1 Sec
Let’s consider two substrings of length m and n, respectively. Now we can have two situations:-
Both the strings end with the same element:
So for finding their shortest common supersequence, what we have to do is we will shorten each string by removing the last element. Then we will find the shortest common supersequence of shortened lines, and then the removed element will be appended to the shortest common supersequence.
SCS(A[1…..m], B[1…...n]) = SCS(A[1….m-1], B[1...n-1]) + A[m]
Suppose two given strings are not ending at the same character:
In this situation the shortest common supersequence will be the shorter of the two sequences SCS(A[1...m-1], B[1..n]) + A[m] and SCS(A[1...m], B[1...n-1]) + B[n].
Function arguments - string ‘A’, string ‘B’, integer ‘N’ representing the length of A’s prefix to be considered, integer ‘M’ representing the length of B’s prefix to be considered.
Returns - Shortest supersequence of A[1,2,...N] and B[1,2,...M].