Задача F четный палиндром КАК РЕШИТЬ?

Подстройкой строки называется любая непустая последовательность символов в строке.
Палиндромом называется строка, которая читается одинаково и слева и с права.
У азизхана есть строка S. Его интересует сколько есть подстрок четный длины S которые являются палиндромами. Одинаковые подстроки начинающие с разных позицй считаются разными!

Как решить?