문제1560--Palindromist

1560: Palindromist

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 284  통과: 37
[제출] [채점기록] [묻고답하기]

문제 설명

A palindrome is a phrase that reads the same forward and backward (ignoring spaces). Given the first half of a palindrome (as described below), you must return a complete palindrome that contains only words from a given set of legal words. The returned palindrome must be a phrase where words are separated by single spaces.

You will be given the first half of the palindrome  containing only letters and no spaces. There are two complete palindromes that can be created from this first half. For example, given "ABC", you could produce either "ABCCBA" or "ABCBA" as the complete palindrome. You must then insert spaces into the complete palindrome such that all the words in the phrase exist in the dictionary  will be given as a list of words.

For example, given the dictionary [ "A", "CANAL", "MAN", "PANAMA", "PLAN" ], and "AMANAPLANAC", your program would output "A MAN A PLAN A CANAL PANAMA" as the answer.

If no palindrome can be made, your program should print “IMPOSSIBLE” instead. If more than one palindrome can be made, return the one that comes first lexicographically (please note that a space ‘ ‘ comes before all letters).

입력 설명

The first line of the input gives the number of test cases. The first line of each test cases contains , the first half of the palindrome and a single positive integer  representing the number of words in  separated by a single space.  will contain only at most 50 uppercase alphabet letters. Next  lines contain elements in , each containing only at most 50 uppercase alphabet letters.

출력 설명

For each test case, output the answer on a separate line.

입력 예시 Copy

3
AMANAPLANAC 5
A
CANAL
MAN
PANAMA
PLAN
AAAAA 3
A
AA
AAA
AAAAA 1
AAAA

출력 예시 Copy

A MAN A PLAN A CANAL PANAMA
A A A A A A A A A
IMPOSSIBLE

출처/분류