P83838

最短母串问题

难度 7 级 初三 动态规划入门 状态压缩
讨论 统计 1通过 8提交 12.5%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给定 n 个字符串 (S_1,S_2,...,S_n),要求找到一个最短的字符串 T,使得这 n 个字符串 (S_1,S_2,...,S_n) 都是 T 的子串。

输入

输入文件第一行是一个整数 n,表示给定的字符串个数。接下来 n 行,每行有一个全由大写字母组成的字符串,。

输出

输出文件只有一行,为找到的最短的字符串 T。在保证最短的前提下,如果有多个字符串都满足要求,那么必须输出按字典序排列的第一个。

样例

样例 1
输入
2
ABCD
BCDABC
输出
ABCDABC

提示

对于 100\% 的数据,n\leq 12,每个字符串的长度不超过 50。

来源

省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交