Алгоритм Манакера: Поиск самого длинного палиндрома за линейное время

Алгоритм Манакера опирается на одно мощное свойство палиндромов — их зеркальную симметрию. Если мы уже нашли большой палиндром, и теперь рассматриваем символ внутри его правой половины, мы можем не вычислять радиус палиндрома для этого символа с нуля! Мы можем "подсмотреть" ответ у симметричного символа в левой половине.

Перед началом поиска алгоритм элегантно решает проблему четных и нечетных палиндромов. Слово "КАБАК" имеет нечетную длину и явный центр "Б". А слово "АННА" имеет четную длину, и его центр находится между буквами. Чтобы не писать два разных алгоритма, Манакер вставляет фиктивные символы (например, "#") между всеми буквами и по краям: #А#Н#Н#А#. Теперь абсолютно все палиндромы становятся нечетной длины и имеют физический центр.

Логика линейного прохода состоит в следующем:

1. Алгоритм заводит массив P, где P[i] — это радиус самого большого палиндрома с центром в позиции i.
2. Алгоритм поддерживает две переменные: C (центр самого правого из найденных палиндромов) и R (его правая граница).
3. Когда алгоритм переходит к новой позиции i (которая находится правее C, но еще внутри границы R), он находит ее зеркального двойника (позицию i') относительно центра C.
4. Математика симметрии говорит: радиус палиндрома P[i] будет как минимум равен радиусу зеркального брата P[i'], но ограничен расстоянием от i до правой границы R. Мы сразу записываем это значение в P[i], мгновенно экономя сотни проверок!
5. И только после этого "читерского" старта, алгоритм пытается расширить палиндром вокруг i наивным способом, посимвольно сравнивая края. Если новый палиндром вылезает за старую правую границу R, мы обновляем C и R.

Удивительным образом, несмотря на вложенный цикл (while для расширения краев), внутренний цикл всегда сдвигает правую границу R только вперед. Переменная R никогда не уменьшается и может увеличиться максимум N раз. Это обеспечивает алгоритму Манакера абсолютную асимптотическую сложность O(N).