1. Recover the key A key is a string of n digits. A sliding window ofsize w (2 m

Question

1. Recover the key
A key is a string of n digits. A sliding window ofsize w (2 moves from the start to the end
ofthe key, generating n-w+1 overlapping-fragments in the process. Each fragment is a string of
w digits. We use key[i, i+w-1} to represent the fragment falling in sliding window [i, i+w-1}. For
example, a window of size w=4 sliding along the key 123456 generates the following three
overlapping-fragments: key[1,4}=1234, key[2,5}=2345, key[3,6}=3456. Given an unsorted list
ofall n-w+1 overlapping-fragments generated by sliding a window ofsize w along an-digit key,
your task is to recover the key. We assume key[1, w-1} is not equal to k[n-w+2, n}.

Input Description: The input file consists of k+ 1 lines. The first line indicates the number k of
test cases to follow. Each subsequent line i presents a test case as an unsorted sequence ofn-w+1
overlapping-fragments separated by blank spaces; each overlapping-fragment is a w-digit string.

Output Description: The output should contain k lines, where line i contains the solution for
the ith problem instance: an-digit key such that all n-w+1 specified overlapping-fragments for
the problem instance are generated by sliding a window ofsize w along the key.

Sample input:
2
1234 3456 2345
02622673 07565434 07922026 09654750 20262267 20965475 22026226 22673487 26226734
26734875 34742096 34875863 42096547 43474209 47420965 47507922 48758635 50756543
50792202 54347420 54750792 56543474 62267348 65434742 65475079 67348758 73487586
74209654 75075654 75079220 75654347 79220262 92202622 96547507

Sample output:
123456
75075654347420965475079220262267348758635

Explanation / Answer

Good wishes,

lets consider the second test case to explain

02622673 07565434 07922026 09654750 20262267 20965475 22026226 22673487 26226734
26734875 34742096 34875863 42096547 43474209 47420965 47507922 48758635 50756543
50792202 54347420 54750792 56543474 62267348 65434742 65475079 67348758 73487586
74209654 75075654 75079220 75654347 79220262 92202622 96547507

We can recover the key from given unsorted overlapping fragments by following a simple procedure which contains the below 8 steps

step 1: place the unsorted fragments in an array by separating them on the basis of blank space between them.

for eg.

a[34]={02622673, 07565434, 07922026, 09654750, 20262267, 20965475, 22026226, 22673487, 26226734, 26734875, 34742096, 34875863, 42096547, 43474209, 47420965, 47507922, 48758635, 50756543,50792202, 54347420, 54750792, 56543474, 62267348, 65434742, 65475079, 67348758, 73487586,74209654, 75075654, 75079220, 75654347, 79220262, 92202622, 96547507};

step 2: place the first element in array 'a' in start and also and place it in result.

i=0

start=a[i]

i.e start=02622673

result=02622673

step 3: extract the substring from 'start' all except the first letter and place it in search

search=2622673

step 4: now search in array 'a' for an element which starts with 'search', then from that element extract the

remaing part other than 'search' and append it to result.

here the matching element in 'a' to substring '2622673' is '26226734' place this in start and as the remaining part is '4' and append it to 'result'

so result=026226734

step 5: repeat steps 3 and 4, until search element is not found in 'a', tis indicates that it the trailing part of the key place this in trail

so trail=0262267348758635

if at thi stage all the elements in array 'a' are visited once then 'trail' itself is the key so goto step 8 else goto step 6

step 6: Now take the next element in array by incrementing 'i' by 1 and then place it in test

step 7: if test is not a substring of 'result' then place it in start and goto the step 3,

else if the test is a substring of 'result' then goto step 6

so here i=2

here start=07565434, as '07565434' is not in 'result' goto step 3

step 8: trail is the required key, stop.

Now run a loop for the 'n' number of times mentioned in the first line of input to repeat this procedure

Then the output contain 'n' lines, where line i contains the solution for
the ith problem instance: an-digit key such that all n-w+1 specified overlapping-fragments for
the problem instance are generated by sliding a window ofsize w along the key.

These steps can easily be converted to a program in any language.

Hope this is clear.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.