паралиндром

[sverhuVniz]

вот ещё одна интересная задачка.
кто даст черновик или идею?
Задача J. Подпалиндромы
Имя входного файла: j.in
Имя выходного файла: j.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.

Дана строчка. Ее подстрокой называется некоторая непустая последовательность подряд идущих символов. Напишите программу, которая определит, сколько подстрок данной строки является палиндромами.

Формат входных данных

Вводится одна строка, состоящая из маленьких латинских букв. Длина строки не превышает 100000 символов.

Формат выходных данных

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

Примеры
j.in----j.out

aaa---6

aba---4