Изменения

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