PLEASE SOMEONE HELP ME INORDER TO SOLVE THIS
Nth Shortest Super Sequence
Time out : 4 Sec
Memory Limit : 64MB
A shortest common supersequence of two strings is defined as the shortest possible string containing both strings as subsequences
(See Notes below for a rigorous definition of a supersequence). There can be more than one shortest supersequence for two strings.
For example the strings “ABC” and “ACB” have “ABCB” and “ACBC” as shortest supersequences (both have a length
of 4 characters and contain both the strings as subsequence). Now if you sort them lexicographically
then “ABCB” comes before “ACBC”.
Given two strings S1 and S2 and a number n, your task is to find the nth shortest supersequence of these two strings (1 based index).
The first line contains one integer t, the number of testcases. (1 <= t <= 200)
This will be followed by t test cases, each containing 3 lines.
- The first line of each test case gives the first string S1
- The second line gives the second string S2
- The third line will give the number n (1 based index)
- The Strings S1 and S2 will contain only uppercase and lowercase english letters only.
- Length of the strings S1 and S2 will be between 1 and 1000.
- n will fit into a 32 bit signed integer.
For each test case print the nth shortest supersequence on a separate line. If the total number of shortest supersequences is less than n then print “NO ANSWER” (without quotes).
- In lexicographical ordering, uppercase letters come before lowercase letters (The order - from low to high - is A to Z followed by a to z).
- Consider two strings A and B of length n and m respectively. We can denote the ith character of
the strings by A[i] or B[i] respectively.Now consider S be the supersequence of A and B. Then we should be able to
list n indices X1to Xn such that the indices are in strictly increasing order
(X123…n) and S[Xi] = A[i] for all i from 1 to n. Similarly we should be able to list m indices Y1to Ym such that the indices are in strictly increasing order(Y123…m) and S[Yi] = B[i]
for all i from 1 to m. A shortest supersequence is a supersequence of minimum length.