Изменения

Пусть дана строка <tex>s</tex>. Требуется найти все подстроки количество подстрок <tex>s</tex>, являющиеся палиндромами. Более формально, аса такие пары <tex>(i, j)</tex>, что <tex>s[i..j]</tex> - палиндром (строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево).

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