方法一：二分 Hash，时间复杂度 \(\mathcal{O}(n \log n)\)
方法二：记 \(R_i\) 为以 \(i\) 结尾的最长回文子串的长度，则 \(R_i \le R_{i - 1} + 2\)，每次从 \(R_{i - 1} + 2\) 开始枚举即可。时间复杂度 \(\mathcal{O}(n)\)。
方法三：SA + \(\mathcal{O}(n) \sim \mathcal{O}(1)\) LCA 做到 \(\mathcal{O}(n)\)
方法四：Manacher
考虑长度为奇数：
考虑当前最右侧的回文串 \(s_{[l, r]}\)，即 \(r\) 最大的串，那么根据对称性，\(d_1[i] = d_1[l + r - i]\)，但是有可能出去，所以要和 \(r - i\) 取 \(\min\)。然后直接暴力 check，时间复杂度 \(\mathcal{O}(n)\)，我不会证。
偶数懒得推了，把开头、结尾、字符间间隔加上特殊字符 #，最后的答案就是 \(\max d_i - 1\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 2.2e7 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, ans, d[N];
char ch;
string s;
void main() {s = "#";while (cin >> ch) s += ch, s += '#';n = s.size();for (int i = 0, l = 0, r = -1; i < n; i++) {int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1); while (0 <= i - k && i - k < n && s[i - k] == s[i + k]) k++;d[i] = k--;if (i + k > r) l = i - k, r = i + k;ans = max(ans, d[i] - 1);}cout << ans << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}