eolymp
bolt
Try our new interface for solving problems
Məsələlər

Суффиксная игра 2

Суффиксная игра 2

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Девочка Ксюша играет в игру со строками.

Ксюша по очереди, одну за одной, выписывает буквы на листочек. На первом шаге она выписывает букву s_1, на втором — s_2, и так далее. Также у Ксюши есть строка t, с помощью которой считается количество очков, заработанное Ксюшей в игре.

Количество очков, которое заработает Ксюша, считается следующим образом. На первом шаге к нему прибавляется количество вхождений строки s_1 в t. На втором шаге к нему прибавляется количество вхождений строки s_1s_2 в t. На третьем шаге — количество вхождений s_1s_2s_3 в t. И так далее. Изначально количество очков равно 0.

Ксюша в любой момент времени может прекратить выписывать буквы. Но, конечно же, она обязана выписать хотя бы одну букву. Помогите ей выбрать стратегию, которая минимизирует количество очков, полученных в игре. Другими словами, найдите такую строку s_1s_2s_3, что если Ксюша будет выписывать символы этой строки, она получит минимально возможное количество очков.

Giriş verilənləri

В первой строке записана строка t (1|t|10^5). Строка t состоит только из маленьких латинских букв.

Çıxış verilənləri

Выведите ответ на задачу — строку s. Если таких строк несколько, выведите минимальную в лексикографическом порядке.

Примечание: Строка x = x_1x_2...x_p лексикографически меньше строки y=y_1y_2...y_q, если либо p < q и x_1=y_1, x_2=y_2, ..., x_p=y_p, либо существует такое число r (r < p, r < q), что x_1=y_1, x_2=y_2, ..., x_r=y_r и x_{r+1} < y_{r+1}. Символы строк сравниваются как их ASCII коды.

Nümunə

Giriş verilənləri #1
z
Çıxış verilənləri #1
a
Mənbə Летняя школа Севастополь 2013, Волна 1, День 7 - Экзамен