← 返回题目列表

AtCoder · code_festival_2018_final_d

D. 三个字母

中文机器翻译题面 查看原题

配点 : 500 点

問題文

由大写和小写英文字母组成的 N 个字符串。 A_1,A_2,...,A_N 的字符串

的 略称 定义如下。当存在

  • 文字列 S 时,1 \leq i < j < k \leq |S| 满足的不论的 i,j,k ,S_i S_j S_k 是 仅由 S 的简称。由

3 个字符组成的字符串中,求出能够成为A_1,A_2,...,A_N 中最多字符串简称的那个。

但是,如果有复数的情况,请求出字典顺序最先的一个。

另外,在字典顺序中,不论字符种类如何,大写英文字母总是排在小写英文字母之前。

制約

  • 1 \leq N \leq 30000
  • 3 \leq |A_i|
  • |A_1|+|A_2|+...+|A_N| \leq 90000
  • A_i 由大写英文字母和小写英文字母组成,在

入力

输入是按以下格式从标准输入给出的。

N
A_1
:
A_N

出力

3 个字符组成的字符串中,求出能够成为A_1,A_2,...,A_N 中,求能够成为最多字符串简称的那个。

但是,如果有复数情况,请按词典顺序选择第一个。


入力例 1

4
aKIHaBaRa
aKIBa
aSaKUSa
SHINKIBA

出力例 1

KIB

3 是某个字符串的缩写 KIB,aKa 但是在这些中按词典顺序最先的 KIB 输出就可以了。

按字典顺序,大写字母始终位于小写字母之前,因此 请注意,它位于K 是a 之前。


入力例 2

3
abc
def
ghi

出力例 2

abc