Manacher
O(n)All palindromic substrings in linear time: d1[i] is the radius of the longest odd palindrome centered at i, d2[i] the even one between i−1 and i. The longest palindromic substring, palindrome counting, and palindromic prefixes all read straight off these arrays.
// use it on
CSES: Longest Palindrome ↗
Report the longest palindromic substring: the maximum over 2·d1[i]−1 and 2·d2[i], with the position recovered from the center.
// the code
// d1[i] = odd radius at i (>= 1); d2[i] = even radius between i-1 and i
pair<vector<int>, vector<int>> manacher(const string& s) {
int n = s.size();
vector<int> d1(n), d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = i > r ? 1 : min(d1[l + r - i], r - i + 1);
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
d1[i] = k--;
if (i + k > r) l = i - k, r = i + k;
}
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = i > r ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) k++;
d2[i] = k--;
if (i + k > r) l = i - k - 1, r = i + k;
}
return {d1, d2};
}
// longest palindrome: max over 2 * d1[i] - 1 and 2 * d2[i]