ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2060. Подпалиндромные пары

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Ваша задача — вычислить количество троек (i, j, k) таких, что ij < k и s[i..j] — палиндром и s[j+1 .. k] — палиндром.

Исходные данные

Вход содержит строку из n строчных латинских букв (1 ≤ n ≤ 3 · 105).

Результат

Выведите количество требуемых троек.

Пример

исходные данныерезультат
abaa
5
Автор задачи: Михаил Рубинчик
Источник задачи: Палиндромный контест, 11 июля 2015