Самая длинная достижимая строка
Вам дан набор строк. Нужно найти максимально длинную строку, которую можно построить, постепенно добавляя символы слева, начиная с пустой строки. При этом на каждом шаге (каждая промежуточная строка) она должна принадлежать исходному набору. Если существует несколько таких строк одинаковой максимальной длины, следует вывести ту, которая идёт первой в лексикографическом порядке.
Входные данные
Первая строка содержит целое число
n (1 ≤ n ≤ 100 000), обозначающее количество строк в исходном наборе.
Следующие n строк содержат сами строки. Каждая строка состоит из строчных английских букв и имеет длину от 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