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

Azerbaijan Programming Olympiad - 2nd Stage preparation

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

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

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

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

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

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

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