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