eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Паліндроми 2

Паліндроми 2

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Рядок називається паліндромом, якщо він однаково читається як зліва праворуч, так і зправа ліворуч. Наприклад, "abba" - паліндром, а "omax" - ні. Для рядка α будемо позначати α[i..j] його підрядок довжини j - i + 1 з i-ї по j-ту позицію включно (позиції нумеруються з 1).

Для заданого рядки α довжини n (1n5000000) потрібно підрахувати кількість q пар (i, j), 1i < jn, таких що α[i..j] є паліндромом.

Вхідні дані

Рядок α довжини n, який складається з маленьких латинських літер.

Вихідні дані

Кількість шуканх пар q.

Приклад

Вхідні дані #0
ab

Вихідні дані #0
2

Вхідні дані #1
abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba
Вихідні дані #1
769