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

Задача:

Пусть дана строка [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] — массивы для записи ответа
 for i = 1 to n
   d1[i] = 1
   while i - d1[i] > 0 and i + d1[i] <= n and s[i - d1[i]] == s[i + d1[i]]
     d1[i]++
   d2[i] = 0
   while i - d2[i] - 1 > 0 and i + d2[i] <= n and s[i - d2[i] - 1] == s[i + d2[i]]
     d2[i]++