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