最長到達可能文字列 (Longest Reachable String)
与えられた文字列の集合があります。空文字列から開始し、左側に文字を追加していく過程で生成されるすべての中間文字列が、初期の集合に含まれるように構築できる“最も長い文字列”を求めてください。最大となる文字列が複数ある場合は、辞書順が最も小さいものを出力します。
入力
最初の行には整数
n (1 ≤ n ≤ 100 000) が与えられ、これは初期集合に含まれる文字列の数を表します。次の n 行には、初期集合に含まれる文字列がそれぞれ1行ずつ与えられます。各文字列は英小文字で構成され、長さは1以上30以下です。出力
与えられた文字列の集合を用いて構築できる最も長い文字列を出力してください。もし該当する文字列が存在しない場合は、空文字列を出力してください。
例
入力 | 出力 |
7
pr
profound
f
found
fo
foun
fou | found |
3
ab
abc
abcd | ㅤ |
5
a
ab
aba
abaz
abad | abad |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB