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, which takes in an input string s, we'll keep two pointers l, r representing the endpoints of a candidate window for the longest palindromic substring, exclusive. We'll initialize them to l = 0, r = 0 for considering odd length palindromes and l = 0, r = 1 for considering even length palindromes (or interweave the string characters with a special character so that palindromes are always of odd length like in Manacher's). These represent empty substrings at the start of s.

At any point, we have two cases. If extending our candidate window by adding s[l], s[r] would make our candidate a palindrome (which we can check by hashing), then expand our candidate window by updating --l, ++r. Otherwise, shift the window to the right by updating ++l, ++r. While doing this, keep track of a running maximal length of valid palindromic substrings res = r - l + 1 and their corresponding starting index resl. When the window has shifted all the way to the right (r >= s.length()), return the substring with maximal length res starting at resl.

This algorithm is correct since it effectively considers every possible palindrome center i from left to right, either stretching the window until it covers the largest palindrome centered at i or doing nothing and skipping i if the largest palindrome centered at i is smaller than some palindrome we've already encountered.

This algorithm is linear time since r is incremented during every iteration.

See an implementation of this algorithm for 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;
}