Изменения
Нет описания правки
Пусть дана строка <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> - аналогичная величина для палиндромов четной длины. Далее научимся вычислять значения этих массивов.
== Наивный алгоритм ==
