#P2322. [HNOI2006] 最短母串问题

    ID: 1333 远端评测题 1000ms 32MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>字符串动态规划dp2006各省省选湖南状态压缩状压

[HNOI2006] 最短母串问题

题目描述

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

输入格式

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

输出格式

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

2
ABCD
BCDABC
ABCDABC

提示

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