Как найти наибольшую палиндром-подстроку — Манакер или хеши с бинпоиском?

При n до 10^6 берите Манакер: O(n) и без риска коллизий. Хеши с бинпоиском (O(n log n)) проще написать на ходу, но на палиндромных задачах жюри любит анти-хеш тесты, плюс лишний логарифм по времени.

Из массивов Манакера ответ достаётся так: длина нечётного палиндрома с центром i равна 2*d1[i]-1, чётного — 2*d2[i]. Берём максимум и восстанавливаем границы.

pair<int,int> longest_palindrome(const string& s) {
    auto d1 = manacher_odd(s);
    // d2 — аналогично для чётных; опустим ради краткости
    int bestLen = 0, bestL = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        int len = 2 * d1[i] - 1;            // нечётный
        if (len > bestLen) { bestLen = len; bestL = i - d1[i] + 1; }
    }
    // не забыть пройтись по d2 для чётных палиндромов!
    return {bestL, bestL + bestLen - 1};   // [l, r] включительно
}

Итог: O(n) время, O(n) память. Главное — не забыть оба случая (нечёт и чёт), иначе на тесте abba потеряете ответ.