e-olymp
Соревнования

February 21 - March 3. Dynamic Programming

Суперпалиндромы

Назовём палиндромом строку длиной более одного символа, которая одинаково читается как справа налево, так и слева направо. Назовём суперпалиндромом строку, которая может быть представлена как конкатенация одного или более палиндромов. Дана строка S. Необходимо найти количество подстрок в S, которые являются суперпалиндромами.

Входные данные

Строка S содержит последовательность от 1 до 1000 строчных латинских букв без пробелов.

Выходные данные

Выведите одно число - количество подстрок S, являющихся суперпалиндромами.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
abc
Выходные данные #1
0
Входные данные #2
abacdc
Выходные данные #2
3
Автор Павел Кузнецов