2014年好像没有回文树， 但是回文树出来之后就变成裸题了
#include <algorithm> #include <cstring> #include <cstdio> #include <iostream> #define rep(i, s, t) for(int i = (s), i##E = (t); i <= i##E; ++i) #define dec(i, s, t) for(int i = (s), i##E = (t); i >= i##E; --i) using namespace std; const int SIGMA = 26; const int MX_N = (3e5 + 10) * 2; char s[MX_N]; namespace PAM { int lst, tot; int len[MX_N], val[MX_N]; int fail[MX_N], ch[MX_N][SIGMA]; void init() { tot = 1; fail[0] = fail[1] = 1; len[1] = -1, lst = 0; } void solve() { init(); rep(i, 1, strlen(s + 1)) { int x = s[i] - 'a', h = lst, u = 0; while(s[i-len[h]-1] != s[i]) h = fail[h]; if(!ch[h][x]) { len[u=++tot] = len[h] + 2; int v = fail[h]; while(s[i-len[v]-1] != s[i]) v = fail[v]; fail[u] = ch[v][x], ch[h][x] = u; }++val[lst = ch[h][x]]; } } }using namespace PAM; long long count() { long long ret = 0; dec(i, tot, 2) val[fail[i]] += val[i]; rep(i, 2, tot) ret = max(ret, (long long)val[i] * len[i]); return ret; } int main() { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("res.out", "w", stdout); #endif scanf("%s", s + 1); solve(); printf("%lld\n", count()); return 0; }