299
правок
Изменения
→Оценка асимптотики
На первый взгляд не очевидно, что данный алгоритм имеет линейную асимптотику: при вычислении ответа для определённой позиции в нем нередко запускается тривиальный алгоритм поиска палиндромов.
Однако более внимательный анализ показывает, что алгоритм всё же линеен. (Стоит сослаться на алгоритм построения [[алгоритм построения Z-функция|Z-функции строки]]строки, который внутренне сильно напоминает данный алгоритм, и работает также за линейное время.)
В самом деле, легко проследить по алгоритму, что каждая итерация, производимая тривиальным поиском, приводит к увеличению на один границы <tex>r</tex>. При этом уменьшений <tex>r</tex> по ходу алгоритма происходить не может. Следовательно, тривиальный алгоритм в сумме совершит лишь <tex>O(n)</tex> действий.
