Задачи
Палиндромы
Палиндромы
Строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Например, "abba" - палиндром, а "omax" - нет. Для строки α будем обозначать α[i..j] ее подстроку длины j - i + 1 с i-ой по j-ую позицию включительно (позиции нумеруются с 1).
Для заданной строки α длины n вычислите количество q пар (i, j), 1 ≤ i < j ≤ n, таких что α[i..j] является палиндромом.
Входные данные
Строка α длины n (1 ≤ n ≤ 10^5
), состоящая из маленьких латинских букв.
Выходные данные
Количество искомых пар q.
Пример
Входные данные #1
aaa
Выходные данные #1
3
Входные данные #2
abba
Выходные данные #2
2
Входные данные #3
omax
Выходные данные #3
0