Начало
Лето 5
A. Таймер B. Mark-up C. Палиндромы D. Цветные перестановки E. Странная игра F. Центры в дереве G. Почтальон
C. Палиндромы
Суффиксное дерево, суффисный массив, суффиксный автоматОлимпиадные задачи на русском языке
| 02/07/2007 | Лето 2007 дорешивание ( 5C) |
| 11/07/2007 | Лето 2007 - 5 (C) |
| 16/05/2009 | Занятие 18 (C) |
| 22/04/2013 | Занятие 25 (B) |
| 04/04/2023 | Строки 2 (проводит BOGAT) (B) |
| 07/05/2024 | Строки 2 (проводит BOGAT) (B) |
Ограничения: время – 5s/10s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (3)
Строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Например, abba – палиндром, а omax – нет. Для строки `α` будем обозначать `α[i:j]` ее подстроку длины `j\ -\ i\ +\ 1` с `i`-й по `j`-ю позицию включительно (позиции нумеруются с 1).
Для заданной строки `α` длины `N\ (1\ ≤\ N\ ≤\ 100000)` требуется подсчитать число `Q` пар `(i,j),\ 1\ ≤\ i\ <\ j\ ≤\ N`, таких что `α[i:j]` является палиндромом.
Ввод содержит одну строку `α` длины `N`, состоящую из маленьких латинских букв.
Выведите искомое число `Q`.
Пример ввода 1
aaa
Пример вывода 1
3
Пример ввода 2
abba
Пример вывода 2
2
Пример ввода 3
omax
Пример вывода 3
0
