Алгоритм Манакера

Задача:

Пусть дана строка [math]s[/math]. Требуется найти [math]d1[i][/math] - длина наибольшего палиндрома нечетной длины с центром в позиции [math]i[/math] и [math]d2[i][/math]- аналогично для палиндромов четной длины для всех [math]i[/math] от 1 до [math]|s|[/math].

Наивный алгоритм

Идея

Опишем сначала наивный алгоритм решения задачи. Чтобы посчитать ответ для позиции [math]i[/math], будем на каждом шаге увеличивать длину палиндрома с центром в [math]i[/math] и убеждаться, что рассматриваемая строка не перестала быть палиндромом, либо не произошел выход за границы массива. Очевидно, что такой алгоритм будет работать за [math]O(n^2)[/math]

Псевдокод

// [math]s[/math] — исходная строка
// [math]d1, d2[/math] — массивы для записи ответа
function [math]\mathtt{calculate}():[/math]
   for [math]i \in 1...|s|[/math]