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

Input file name:	palindromes.in
Output file name:	palindromes.out
Time limit:	2 s
Memory limit:	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

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

Discuss       Submit a solution



Printable version