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

Задача:

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