Изменения

Пусть дана строка <tex>s</tex>. Требуется найти <tex>d1[i]</tex> - — длина наибольшего палиндрома нечетной длины с центром в позиции <tex>i</tex> и <tex>d2[i]</tex>- — аналогично для палиндромов четной длины для всех <tex>i</tex> от 1 до <tex>|s|</tex>.

Будем поддерживать границы самого правого из найденных палиндромов - — <tex>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d1[i]</tex> - — т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</tex> уже посчитаны. Возможны два случая:

# <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>n</tex> раз, где <tex>n</tex> - — длина строки. Попытаемся понять, сколько раз будет выполнен внутренний цикл, ответственный за наивный подсчет значений. Заметим, что каждая итерация вложенного цикла приводит к увеличению <tex>r</tex> на 1. Действительно, возможны следующие случаи:

* [[Z-— функция]]