0016. Палиндромы

Имя входного файла:	palindromes.in
Имя выходного файла:	palindromes.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Однажды Вася пошел в школу и обнаружил на одной из стен слово. Возвращаясь со школы, он посмотрел на это же слово и прочитал его с другой стороны. Вася обнаружил, что оно читается одинаково с обеих сторон. Такие слова называются палиндромами. Например, aba, a, abacaba являются палиндромами, а ab, baba, cab – не являются. На следующей стене Вася заметил еще одно слово и задался вопросом: а на какое минимальное количество палиндромов можно его разбить?

Ваша задача – помочь Васе, написав отвечающую на этот вопрос программу.

Формат входного файла

Входной файл содержит единственную непустую строку, содержащую слово из строчных символов латинского алфавита(a, b, c,..., z). Длина строки не превосходит 1000.

Формат выходного файла

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

Пример:

palindromes.in	palindromes.out
aba	1 aba
abakada	3 aba k ada

Источник: Командное школьное первенство Республики Карелия по программированию, октябрь 2008.

Обсудить       Отправить решение