8
правок
Изменения
Нет описания правки
Пусть дана строка <tex>s</tex>. Требуется найти <tex>d1[i]</tex> - длина наибольшего палиндрома нечетной длины с центром в позиции <tex>i</tex> и <tex>d2[i]</tex>- аналогично для палиндромов четной длины для всех <tex>i</tex> от 1 до <tex>|s|</tex>.
}}
== Наивный алгоритм ==
===Идея===
Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции <tex>i</tex>, будем на каждом шаге увеличивать длину палиндрома с центром в <tex>i</tex> и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за <tex>O(n^2)</tex>
===Псевдокод===
