107 - ZOJ Monthly, July 2011 - E
There are N magical words, s1, s2 ... sN, each of them consists of seven distinguish low-case letters.
A mighty string is a string that contains all the magical words in order. That means, string str[1..L] is a mighty string if and only if there exists 0 < k1 < k2 < ... < kN < L, where si is a prefix of str[ki..L].
I know you are very skilled in algorithms and you can easily find the shortest mighty string in no time. But can you find the shortest palindromic mighty string? That is, the shortest mighty string whose reverse is itself.
No more than 130 cases. For each case, first line is N and then N magical words in the second line.
For each case, output the shortest palindromic mighty string in one line. If multiple answers exist, output the lexicographically smallest one.
The length of each answer is guaranteed to be no longer than 100 characters.
3 abcdefg cdefghi hgfedcb 2 abcdefg abcdefg
Author: CUI, Tianyi
Contest: ZOJ Monthly, July 2011