Codeforces Round 189 (Div. 1) |
---|
Закончено |
Подстрока строки — это непрерывная подпоследовательность символов данной строки. Таким образом, строка bca является подстрокой строки abcabc, а строка cc — нет.
Повторяющийся блок — это строка, полученная конкатенацией некоторой строки с собой же. Таким образом, строка abcabc — это повторяющийся блок, а строки abcabd, ababab — нет.
Вам дана последовательность символов латинского алфавита (строка). За один ход Вы находите наикратчайшую подстроку, которая является повторяющимся блоком. Если таких подстрок несколько, выбираете ближайшую к левому краю строки. Пусть найденная подстрока имеет вид XX (X — некоторая строка), тогда Вы заменяете ее строкой X, иными словами, Вы удаляете одну из подстрок X в этой подстроке. Вы повторяете процесс до тех пор, пока в строке не остается повторяющихся блоков.
Как будет выглядеть результирующая строка? Посмотрите пояснения к тестовым примерам, чтобы лучше понять условие.
В первой строке дана строка, состоящая из строчных символов латинского алфавита, длины от 1 до 50000, включительно.
Выведите итоговую строку после применения операций.
abccabc
abc
aaaabaaab
ab
birdbirdbirdistheword
birdistheword
В первом примере строка превращается так: abccabc → abcabc → abc.
Во втором примере строка превращается так: aaaabaaab → aaabaaab → aabaaab → abaaab → abaab → abab → ab.
Название |
---|