8
правок
Изменения
Нет описания правки
Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции <tex>i</tex>, будем на каждом шаге увеличивать длину палиндрома с центром в <tex>i</tex> и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за <tex>O(n^2)</tex>
===Псевдокод===
<font color=green>// <tex>s</tex> {{---}} исходная строка</font>
<font color=green>// <tex>d1, d2</tex> {{---}} массивы для записи ответа</font>
'''function''' <tex>\mathtt{calculate}():</tex>
'''for''' <tex>i \in 1...|s|</tex>
