Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача J. Подпалиндромы
| Имя входного файла: | j.in |
| Имя выходного файла: | j.out |
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.
Дана строчка. Ее подстрокой называется некоторая непустая последовательность подряд идущих символов. Напишите программу, которая определит, сколько подстрок данной строки является палиндромами.
Формат входных данных
Вводится одна строка, состоящая из маленьких латинских букв. Длина строки не превышает 100000 символов.
Формат выходных данных
Выведите одно число - количество подстрок данной строки, являющихся палиндромами
Примеры
| j.in | j.out |
aaa |
6 |
aba |
4 |