Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
225. Палиндромы
Суффиксное дерево, суффисный массив, суффиксный автоматОлимпиадные задачи на русском языке
| 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) |
Ограничения: время – 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
