
ZOJ Problem Set  3514
There are N magical words, s_{1}, s_{2} ... s_{N}, each of them consists of seven distinguish lowcase 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 < k_{1} < k_{2} < ... < k_{N} < L, where s_{i} is a prefix of str[k_{i}..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. InputNo more than 130 cases. For each case, first line is N and then N magical words in the second line. OutputFor 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. Sample input3 abcdefg cdefghi hgfedcb 2 abcdefg abcdefg Sample outputabcdefghihgfedcba abcdefgfedcbabcdefgfedcba Author: CUI, Tianyi Contest: ZOJ Monthly, July 2011 