WORD - Wordplay
Ivana made up a long word of N letters. Then she wrote down all K-letter-substrings of that word. For example, if the original word is BANANA and K=3, Ivana writes down the words BAN, ANA, NAN, ANA. The number of these words is, obviously, N-K+1.
Ivana sorted these words in lexicographic order (in the given example, that would be ANA, ANA, BAN, NAN).
But the sad thing happened: Ivana forgot the original word! Your task is to reconstruct it. A unique solution will exist in all of the test data.
Constraints: 3 ≤ N ≤ 100 000, 2 ≤ K ≤ 15, K < N.
Input
[integers N, K]
[N-K+1 words in lexicographic order, each consisting of capital English letters]
Output
[the required word]
Example
Input: 6 3 ANA ANA BAN NAN Output: BANANA
hide comments
Flyers:
2013-09-18 21:50:40
best problem ever....
|
|
Ravi Kiran:
2011-09-14 09:34:08
Really Like the Problem. Tested lots of things in my opinion.
|
|
abhijith reddy d:
2011-09-14 09:34:08
Cool Problem. |
Added by: | Adrian Satja Kurdija |
Date: | 2011-04-19 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem |