#1316. 「一本通 2.4 练习 4」最短母串

    ID: 1316 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>DP状态压缩AC 自动机HNOI早于 2010

「一本通 2.4 练习 4」最短母串

题目描述

原题来自:HNOI 2006

给定 nn 个字符串 S1,S2,,SnS_1,S_2,\cdots ,S_n,要求找到一个最短的字符串 TT,使得这 nn 个字符串都是 TT 的子串。

输入格式

第一行是一个正整数 nn,表示给定的字符串的个数;

以下的 nn 行,每行有一个全由大写字母组成的字符串。

输出格式

只有一行,为找到的最短的字符串 TT

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

样例

2
ABCD
BCDABC
ABCDABC

数据范围与提示

对于全部数据,1n12,1Si501\le n\le 12,1\le |S_i|\le 50