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.

#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;
}