Изменения
Нет описания правки
1. <tex>i > r</tex>, т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции <tex>i</tex>.
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>. После этого запустим наивный алгоритм, который будет увеличивать значение <tex>d1[i]</tex>, пока это возможно. После каждого шага важно не забывать обновлять значения <tex>[l;r]</tex>
Заметим, что массив <tex>d2</tex> считается аналогичным образом, нужно лишь немного изменить индексы.
===Псевдокод===
Приведем код, который вычисляет значения массивов массива <tex>d1</tex> и : <font color=green>// <tex>d2s</tex>{{---}} исходная строка</font> '''int''' l = 0 '''int''' r = -1 '''for''' i = 1 '''to''' n '''int''' k = 0 '''if''' i <= r k = min(r - i, d[r - i + l]) '''while''' i + k + 1 <= n '''and''' i - k - 1 > 0 '''and''' s[i + k + 1] == s[i - k - 1] k++ d1[i] = k '''if''' i + k > r l = i - k r = i + k
Вычисление значений массива <tex>d2</tex>:
<font color=green>// <tex>s</tex> {{---}} исходная строка</font>
'''int''' l = 0
'''int''' r = -1
'''for''' i = 1 '''to''' n
'''int''' k = 10
'''if''' i <= r
k = k + min(r - i+ 1, d[r - i + l+ 1]) '''while''' i + k <= n '''and''' i - k - 1 > 0 '''and''' s[i + k] == s[i - k- 1]
k++
