Алгоритм Манакера
(Время: 2 сек. Память: 32 Мб Сложность: 79%)
Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки «abba» и «ata» являются палиндромами.
Подстрокой некоторой строки называется непустая последовательность подряд идущих символов в исходной строке.
Напишите программу, которая определит, сколько подстрок данной строки является палиндромами.
Входные данные
В единственной строке входного файла INPUT.TXT записана строка, состоящая из символов с кодами ASCII от 33 до 127. Длина строки не превышает 106.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | AAAA | 10 |
| 2 | ABRACADABRA | 13 |
| 3 | ABACABADABACABA | 32 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
