Изменения

# <tex>i \leqslant r</tex>. Тогда попробуем воспользоваться значениями, посчитанным ранее. Отразим нашу текущую позицию внутри палиндрома <tex>[l;r] : j = (r - i) + l</tex>. Поскольку <tex>i</tex> и <tex>j</tex> — симметричные позиции, то если <tex>d1[j] = k</tex>, мы можем утверждать, что и <tex>d1[i] >= k</tex>. Это объясняется тем, что палиндром симметричен относительно своей центральной позиции (т.е. его левая половина равна его правой половине, записанной в обратном порядке). Однако надо не забыть про один граничный случай: что если <tex>i + d1[j] - 1</tex> выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами это палинлрома у нас нет(а значит мы не можем утверждать, что симметрия сохраняется), то необходимо ограничить значение <tex>d1[i]</tex> следующим образом: <tex>d1[i] = min(r - i, d1[j])</tex>. После этого запустим наивный алгоритм, который будет увеличивать значение <tex>d1[i]</tex>, пока это возможно.