Изменения
Нет описания правки
Будем поддерживать границы самого правого из найденных палиндромов - <tex>[l; r]</tex>. Итак, пусть мы хотим вычислить <tex>d1[i]</tex> - т.е. длину наибольшего палиндрома с центром в позиции <tex>i</tex>. При этом все предыдущие значения в массиве <tex>d</tex> уже посчитаны. Возможны два случая:
После каждого шага важно не забывать обновлять значения <tex>[l;r]</tex>
l = i - k
r = i + k - 1
===Оценка сложности===
Внешний цикл в приведенном алгоритме выполняется ровно <tex>n</tex> раз, где <tex>n</tex> - длина строки. Попытаемся понять, сколько раз будет выполнен внутренний цикл, ответственный за наивный подсчет значений. Заметим, что каждая итерация вложенного цикла приводит к увеличению <tex>r</tex> на 1. Действительно, возможны следующие случаи:
# <tex>i > r</tex>, т.е. сразу будет запущен наивный алгоритм и каждая его итерация будет увеличивать значение <tex>r</tex> хотя бы на 1
# <tex>i \leq r</tex>. Здесь опять два случая:
## <tex>i + d[j] - 1 \leq r</tex>, но тогда, очевидно, ни одной итерации вложенного цикла выполнено не будет
## <tex>i + d[j] - 1 > r</tex>, тогда каждая итерация вложенного цикла приведет к увеличению <tex>r</tex> хотя бы на 1.
Т.к. значение <tex>r</tex> не может увеличиваться более <tex>n</tex> раз, то описанный выше алгоритм работает за линейное время.
