CF638B Making Genome in Berland

伯兰的科学家们面临着一项非常重要的任务——根据若干个短 DNA 片段，还原恐龙的 DNA！伯兰恐龙的基因组与我们之前了解的基因组完全不同：它拥有 $26$ 种不同类型的核苷酸，每种核苷酸最多只能出现一次。如果我们给每种核苷酸分配一个不同的英文字母，那么伯兰恐龙的基因组就表示为一个非空的小写英文字母字符串，并且每个字母最多出现一次。 科学家们手中有 $n$ 个基因片段，这些片段作为所需基因组的子串（即连续的若干核苷酸）给出。 你的任务是：帮助科学家们还原出恐龙的基因组。题目保证输入是无矛盾的，并且至少存在一个可行的基因组。当科学家们得知你是强力程序员时，他们额外要求你选取最短的可行基因组。如果有多个最短的字符串，可以任选一个。

输入的第一行为一个正整数 $n$（$1 \leq n \leq 100$），表示基因片段的数量。 接下来的 $n$ 行中，每行描述一个基因片段。每个片段是由不同小写英文字母组成的非空字符串。题目没有保证所给片段互不相同。片段之间可以任意重叠，一个片段也可能是另一个片段的子串。 题目保证存在一个包含所有给定片段作为子串的、且所有字母互不相同的字符串。

输出一行，表示包含所有给定片段的最短基因组，并且基因组中所有核苷酸互不相同。如果有多个满足条件的字符串，输出最短的即可。如果最短的也有多个，输出其中任意一个都可以。

由 ChatGPT 5 翻译