У Азизхана есть строчка S. Его интересует сколько есть подстрок четной

Бесхитростный метод: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. Таковой метод будет работать O(S^2), что при ограничении S lt;= 10^5 потребует приблизительно 10^10 / 2 сопоставлений, что довольно длинно.

Оптимизация: в центре у палиндрома четной длины всегда пара схожих знаков. Их можно отыскать, а затем наращивать длину до тех пор, пока это возможно. Плюс этого наблюдения в том, что если пара попадется не в центре, то наибольшая длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. Но в худшем случае (все символы одинаковы) всё равно придется произвести большое число сопоставлений.

Но задачку можно решить и за линейное время. Например, существует метод Манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. А конкретно, если в длинноватую-длинную строку-палиндром заходит другая подстрока-палиндром, то можно не начинать проверку поновой, а использовать теснее имеющуюся информацию.

Пример 1: "длинноватая" подстрока-палиндром:
cbbaabbaabbc
в которой знаменита подстрока-палиндром. Тогда в строке есть симметричная подстрока-палиндром:
cbbaabbaabbc
Пример 2: "длинная" подстрока палиндром:
bbaabbaabbaa
Зная, что в ней есть подстрока-палиндром
bbaabbaabbaa,
можно явные сопоставленья для подстроки с центром в
bbaabbaabbaa
начинать теснее с 
bbaabbaabbaa

Если не охото писать без помощи других, метод Манакера просто находится.