Many sources note that LPS can be solved in linearithmic time with hashing and binary search.

Surprisingly, I have not found any sources claiming that LPS can be solved in linear time with hashing, despite such an algorithm being possible and elementary. We'll introduce such an algorithm here.

In our algorithm, we'll keep two pointers l, r representing the endpoints of the palindrome we are currently considering, exclusive. Initialize them to l = 0, r = 0 for considering odd length palindromes or l = 0, r = 1 for considering even length palindromes (or interweave the string characters with a special character like in Manacher's).

See an implementation to Longest Palindrome on CSES below or here.

#include <bits/stdc++.h>
 
using namespace std;
 
constexpr long long P = 31, INV = 357027418778899, MOD = 922320831845489;  // https://bigprimes.org/
 
pair<int, int> solve(string &s, bool odd) {
    long long lhash = 0, rhash = lhash, power = 1;
    int res = 1, resl = 0;
    for (int l = 0, r = odd ? 0 : 1; r < static_cast<int>(s.length());) {
        if (l >= 0 && lhash == rhash && s[l] == s[r]) {
            int potential = r - l + 1;
            if (potential > res) {
                res = potential;
                resl = l;
            }
 
            // extend
            lhash = (P * lhash + s[l--]) % MOD;
            rhash = (P * rhash + s[r++]) % MOD;
            power = (P * power) % MOD;
        } else {
            // shift
            lhash = static_cast<long long>((static_cast<__int128>(INV) * (lhash + power * s[((l + r) >> 1) + 1] - s[l + 1]) % MOD + MOD) % MOD);
            rhash = ((P * rhash - power * s[(l + r + 1) >> 1] + s[r]) % MOD + MOD) % MOD;
            ++l;
            ++r;
        }
    }
 
    return {resl, res};
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s;
    cin >> s;
 
    auto odd = solve(s, false), even = solve(s, true);
    cout << (odd.second >= even.second ? s.substr(odd.first, odd.second) : s.substr(even.first, even.second)) << endl;
 
    return 0;
}