Изменения

Легко увидеть, что таких подстрок в худшем случае будет <tex>n^2</tex>. Значит, нужно найти компактный способ хранения информации о них. Пусть <tex>d1[i]</tex> — количество палиндромов нечетной нечётной длины с центром в позиции <tex>i</tex>, а <tex>d2[i]</tex> — аналогичная величина для палиндромов четной чётной длины. Далее научимся вычислять значения этих массивов.

Рассмотрим сначала задачу поиска палиндромов нечетной нечётной длины. Центром строки нечетной нечётной длины назовем символ под индексом <tex>\left\lfloor \dfrac{|t|}{2}\right\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.

Для палиндромов четной чётной длины алгоритм такой же. Центр строки четной чётной длины {{---}} некий мнимый элемент между <tex>\dfrac{|t|}{2} - 1</tex> и <tex>\dfrac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.

''<font color=green>//shift = 0 при поиске палиндрома нечетной нечётной длины, иначе shift = 1</font>''