Задача №112767. Миша против древних берляндцев
Миша изучает работы по расшифровке древнеберляндских текстов. Древние берляндцы пользовались иероглифичной письменностью. Поскольку число иероглифов очень велико, в трудах, изучаемых Мишей, каждый иероглиф записывается в виде последовательности строчных латинских символов. Древнеберляднское слово представляет собой последовательность из одного или нескольких иероглифов, записанных один за другим слева направо без разделителей. Известно, что древние берляндцы очень любили палиндромы, поэтому все древнеберляндские слова являются палиндромами: первый иероглиф слова совпадает с последним, второй иероглиф — с предпоследним и так далее.
К сожалению, Миша не нашел правила сопоставления иероглифов последовательностям латинских символов, поэтому чтение трудов дается ему очень тяжело. Отчаявшись найти эти правила, Миша решил попробовать сам угадать разбиение слов на иероглифы, для чего он придумал следующий алгоритм: он выписывает каждое отдельное слово и пытается разбить его на наибольшую по длине последовательность иероглифов так, чтобы эта последовательность при объединении давала исходное слово и при этом являлась палиндромом. Но поиск такого разбиения оказался слишком сложным для Миши, поэтому он обратился за помощью к Вам.
В первой и единственной строке записано слово, состоящее из не более чем \(4 \cdot 10^5\) строчных латинских букв — древнеберляндское слово, не разбитое на иероглифы.
В первой строке вывести число \(N\) — количество иероглифов, в последующих \(N\) строках вывести последовательности латинских символов, соответствующие иероглифам исходного слова. При этом объединение всех иероглифов должно давать исходное слово, а последовательность иероглифов должна быть палиндромом. Количество \(N\) должно быть максимально возможным для всех корректных разбиений.
Гарантируется, что решение, работающее для слов, состоящих из не более чем 150 000 латинских букв, набирает 60 баллов.
abacaba
7 a b a c a b a
nnoi
1 nnoi
abcab
3 ab c ab