Алгоритм Манакера
Алгоритм Манакера решает следующую задачу --- для каждой позиции $i$ строки $S$ найти такое $d$, что $$S[i - d: i + d] \text{ --- палиндром}$$
Подготовка
Можно заметить, что по определению мы узнаем только информацию о нечетных палиндромах (например $abacaba$). О палиндроме $abba$ мы ничего не узнаем --- его центр как будто находится между буквами.
Тогда поставим между всеми соседними буквами символ "*". Теперь все нечетные палиндромы покрывают и нечетные, и четные палиндромы.
Алгоритм
Строить ответ будем итеративно, а алгоритм будет очень похож на z-функцию, поэтому рекомендуется сначала ознакомиться с ним.
Для текущей позиции $i$ будем поддерживать $l, r$ --- такие два числа, что $S[l:r]$ является палиндромом (нечетным). Более того, среди всех таких пар будем хранить ту, где $r$ максимален.
Центр палиндрома $(l, r)$ находится левее позиции $i$, поэтому $i$ где-то в правом крыле. Значит, у него есть левое отражение $i'$, для которого посчитана $d[i']$. Но тогда этот же палиндром читается от позиции $i$. Во всяком случае, до тех пор, пока его правая граница не упирается в $r$. Так мы изначально проинициализируем $d[i]$. Дело за малым --- дальше честно пошагово будем расширять $d[i]$.
Время работы
Линейное, по той же причине, что и z-функция. Каждая внутренняя итерация цикла сдвигает правую границу вправо, а сделать это можно только линейное число раз.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s