Зеркальные фрагменты в школьной записи

В школьном чате кто‑то написал длинную строку из маленьких латинских букв. Классный руководитель любит «зеркальные» фрагменты: такие подряд идущие кусочки строки, которые читаются одинаково слева направо и справа налево.

Посчитайте, сколько в строке таких зеркальных фрагментов (подстрок). Две подстроки считаются разными, если отличаются позициями в строке (даже если текст одинаковый).

Формат ввода

• Одна строка s, состоящая из строчных латинских букв a–z.

Формат вывода

• Одно целое число — количество палиндромных подстрок в s.

Ограничения

• 1 ≤ |s| ≤ 3000.
• Алфавит: a–z.
• Ответ может не помещаться в 32-битный тип (ориентируйтесь на 64-битное целое, как на олимпиадах). В Python это не проблема.

Пример Ввод:

ababa

Вывод:

9

Ключевое наблюдение: любой палиндром однозначно задаётся своим «центром». Центр бывает двух типов: в символе (нечётная длина, например aba) и между соседними символами (чётная длина, например abba). Если для каждого центра попытаться расширять границы влево и вправо, пока символы равны, то каждое успешное расширение даёт новый палиндром, и так мы посчитаем все подстроки по позициям.

Почему это работает: палиндром симметричен, значит проверять всю подстроку не нужно — достаточно сравнивать пары s[l] и s[r], двигая l -= 1, r += 1.

План:

• Пусть n = len(s), ans = 0.
• Для каждого индекса c (0..n-1) считаем нечётные палиндромы:
• l = c, r = c, пока l >= 0, r < n и s[l] == s[r]: увеличиваем ans, сдвигаем l--, r++.
• Для каждого «разрыва» между символами c (0..n-2) считаем чётные палиндромы:
• l = c, r = c+1, дальше так же расширяемся.
• Выводим ans (в Python это обычный int).

Мини-сниппет условия расширения: while l >= 0 and r < n and s[l] == s[r]: ...

Сложность: в худшем случае O(n^2) сравнений (например, строка из одинаковых букв), при n ≤ 3000 это проходит.

Частая ошибка: забыть про чётные палиндромы (центр между символами) — тогда потеряются варианты вроде aa, abba.