Как работает алгоритм Манакера и почему он находит все палиндромы за O(n)?
Хочу за линию посчитать для каждой позиции радиус наибольшего палиндрома с центром в ней. Перебор центров с расширением — O(n^2). Манакер вроде делает O(n), но я не понимаю трюка с зеркалом относительно текущего правого блока. Дайте рабочий код и объяснение.
2 ответа
Манакер для каждого центра хранит радиус палиндрома, переиспользуя симметрию. Удобнее всего считать сразу два массива: d1[i] — нечётные палиндромы (центр в символе), d2[i] — чётные (центр между символами). Поддерживаем самый правый достигнутый палиндром [l, r].
Ключ: если i внутри [l, r], то отражённая позиция j = l + r - i уже посчитана, и d1[i] стартует с min(d1[j], r - i + 1) вместо нуля — это экономит наивные расширения.
vector<int> manacher_odd(const string& s) {
int n = s.size();
vector<int> d(n);
int l = 0, r = -1;
for (int i = 0; i < n; ++i) {
int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) ++k;
d[i] = k;
if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
}
return d; // d[i] = радиус нечётного палиндрома с центром в i (длина = 2*d[i]-1)
}
Сложность — O(n): каждое наивное расширение while двигает r вправо, а r монотонно растёт и ограничено n. Та же амортизация, что в Z-функции.
Альтернатива двум массивам — трюк с вставкой разделителей: преобразовать abc → ^#a#b#c#$, тогда чётные и нечётные палиндромы становятся однотипными и хватает одного прохода manacher_odd. Часовые ^ и $ (символы, не встречающиеся в строке) убирают проверку границ. Код чуть короче, но индексацию обратно в исходную строку надо считать аккуратно: радиус в расширенной строке = длина палиндрома в исходной.