Many sources note that [LPS](https://cses.fi/problemset/task/1111/) 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](https://cses.fi/problemset/task/1111/) below or [here](https://cses.fi/paste/3ea88c5bc478a7a2bbf58f/).↵
↵
```cpp↵
#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;↵
}↵
```
↵
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](https://cses.fi/problemset/task/1111/) below or [here](https://cses.fi/paste/3ea88c5bc478a7a2bbf58f/).↵
↵
```cpp↵
#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;↵
}↵
```
