Изменения

2. <tex>i \leq r</tex>. Тогда попробуем воспользоваться значениями, посчитанным ранее. Отразим нашу текущую позицию внутри палиндрома <tex>[l;r] : j = (r - i) + l</tex>. Поскольку <tex>i</tex> и <tex>j</tex> - симметричные позиции, то мы можем утверждать, <tex>d1[i] = d1[j]</tex>. Однако надо не забыть про один граничный случай: что если <tex>i + d1[j] - 1</tex> выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами это палинлрома у нас нет, то необходимо ограничить значение <tex>d1[i]</tex> следующим образом: <tex>d1[i] = min(r - i, d1[j]).После этого запустим наивный алгоритм, который будет увеличивать значение <tex>d1[i]</tex>, пока это возможно. Заметим, что массив <tex>d2</tex> считается аналогичным образом, нужно лишь немного изменить индексы. ===Псевдокод===Приведем код, который вычисляет значения массивов <tex>d1</tex> и <tex>d2</tex>  <font color=green>// <tex>s</tex> {{---}} исходная строка</font> <font color=green>// <tex>d1, d2</tex> {{---}} массивы для записи ответа</font> '''int''' l = 0 '''int''' r = -1 '''for''' i = 1 '''to''' n '''int''' k = 1 '''if''' i <= r k = k + min(r - i, d[r - i + l]) '''while''' i + k <= n '''and''' i - k > 0 '''and''' s[i + k] == s[i - k] k++ d1[i]++ d2[i] = 0 '''while''' i - d2[i] - 1 > 0 '''and''' i + d2[i] <= n '''and''' s[i - d2[i] - 1] == s[i + d2[i]] d2[i]++