Во время расследования Бенуа Бланк обнаружил подозрительную записку, оставленную кем-то на месте преступления. Текст в записке $$$t$$$ на первый взгляд не имел никакого смысла, но после долгого анализа записки Бланк пришел к выводу, что сообщение осмысленно, но зашифровано.
Шифр, использованный в записке, довольно нестандартный. Каждое слово было зашифровано отдельно, после чего все слова были склеены вместе, чтобы не было понятно, где какое слово начинается и заканчивается. Поэтому первым делом детектив решил восстановить, где находятся границы слов, а после уже взяться за их расшифровку.
Известно, что текст на записке был получен следующим образом: набор зашифрованных слов $$$w_1, w_2, \ldots, w_n$$$ был продублирован в развернутом виде, после чего выписан без пробелов. Иными словами, $$$t = (w_1 + \ldots + w_n) + (w_n + \ldots + w_1)$$$, где знак '+' обозначает конкатенацию.
Помогите Бенуа Бланку восстановить исходный набор зашифрованных слов. Поскольку Бланк считает, что сообщение содержало много слов, из всех способов разбить $$$t$$$ на слова в соответствии с условием выберите тот, в котором количество слов максимально.
Во вводе дана единственная строка $$$t$$$ из маленьких латинских букв — зашифрованный текст ($$$1 \leqslant |t| \leqslant 10^6$$$).
В первой строке выведите целое число $$$n$$$ — максимально возможное количество слов в зашифрованном тексте. В следующих $$$n$$$ строках перечислите сами слова по одному на каждой строке.
Если ответов с максимальным $$$n$$$ несколько, выведите любой из них.
Гарантируется, что ответ существует.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 13 | $$$|t| \leqslant 20$$$ | полная | |
2 | 18 | $$$|t| \leqslant 100$$$ | 1 | полная |
3 | 23 | $$$|t| \leqslant 1000$$$ | 1 – 2 | первая ошибка |
4 | 20 | $$$t$$$ состоит только из букв 'a' и 'b' | первая ошибка | |
5 | 26 | нет | 1 – 4 | первая ошибка |
abaccaba
4 a b a c
guesswhoitisisitwhoguess
4 guess who it is
xaabaababaaabxaa
5 xaa b a a ba