Технокубок 2018 - Отборочный Раунд 3 |
---|
Закончено |
Назовем подстроку некоторой строки самой частой, если количество ее вхождений не меньше количества вхождений любой другой подстроки.
Дано множество строк. Назовем какую-то строку хорошей, если все элементы множества являются ее самыми частыми подстроками. Восстановите непустую минимальную по длине хорошую строку, а из таких — лексикографически минимальную. Если же таких строк не существует, то выведите «NO» (без кавычек).
Подстрокой называется непрерывная подпоследовательность букв строки. Например, «ab», «c», «abc» являются подстроками строки «abc», а «ac» — нет.
Количество вхождений подстроки в строку равно количеству таких позиций в данной строке, в которых встречается данная подстрока. Вхождения подстроки могут перекрываться.
Строка a лексикографически меньше строки b, если a является префиксом b, или в a стоит меньшая буква на первой позиции, где a и b отличаются.
В первой строке дано целое число n (1 ≤ n ≤ 105) — количество строк в данном множестве.
Далее следуют n строк, каждая из которых содержит непустую строку из строчных латинских букв. Гарантируется, что все строки различны.
Суммарная длина всех данных строк не превышает 105.
Выведите непустую минимальную по длине хорошую строку, а из таких минимальную лексикографически, либо «NO» (без кавычек), если таких строк не существует.
4
ai
lru
cf
cfmailru
3
kek
preceq
cheburek
NO
Можно показать, что в первом тесте есть два варианта хорошей строки минимальной длины: «cfmailru» и «mailrucf». Первый вариант является минимальным лексикографически.
Название |
---|