P2322 [HNOI2006] Shortest Superstring Problem

Given $n$ strings $(S_1, S_2, \dots, S_n)$, find the shortest string $T$ such that all $n$ strings $(S_1, S_2, \dots, S_n)$ are substrings of $T$.

The first line contains an integer $n$, the number of given strings. The next $n$ lines each contain a string consisting only of uppercase letters.

Output a single line containing the shortest string $T$. Among all shortest candidates, if there are multiple strings that satisfy the requirement, output the lexicographically smallest one.

For $100\%$ of the testdata, $n \leq 12$, and the length of each string does not exceed $50$. Translated by ChatGPT 5