Задачі
Паліндроми 2
Паліндроми 2
Рядок називається паліндромом, якщо він однаково читається як зліва праворуч, так і зправа ліворуч. Наприклад, "abba" - паліндром, а "omax" - ні. Для рядка α будемо позначати α[i..j] його підрядок довжини j - i + 1 з i-ї по j-ту позицію включно (позиції нумеруються з 1).
Для заданого рядки α довжини n (1 ≤ n ≤ 5000000) потрібно підрахувати кількість q пар (i, j), 1 ≤ i < j ≤ n, таких що α[i..j] є паліндромом.
Вхідні дані
Рядок α довжини n, який складається з маленьких латинських літер.
Вихідні дані
Кількість шуканх пар q.
Приклад
Вхідні дані #0
ab
Вихідні дані #0
2
Вхідні дані #1
abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba
Вихідні дані #1
769