Назовём
палиндромом строку длиной более одного символа, которая одинаково читается как
справа налево, так и слева направо. Назовём суперпалиндромом строку, которая
может быть представлена как конкатенация одного или более палиндромов. Дана
строка S. Необходимо найти количество подстрок в S, которые
являются суперпалиндромами.
Время
тестирования: 2 секунды на один тест
В первой
строке входного файла содержится S
— последовательность от 1 до 1000 строчных латинских букв без пробелов.
Выведите в выходной
файл одно число — количество подстрок S,
являющихся суперпалиндромами.
Примеры
|
input
|
output
|
|
abc
|
0
|
|
abacdc
|
3
|
