Description
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。Input
输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。Output
输出一个整数，为逝查回文子串的最大出现值。Sample Input
【样例输入l】
abacaba
【样例输入2】
wwwSample Output
【样例输出l】
7
【样例输出2】
4HINT
一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。
在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中：
● a出现4次，其出现值为4：1：1=4
● b出现2次，其出现值为2：1：1=2
● c出现1次，其出现值为l：1：l=l
● aba出现2次，其出现值为2：1：3=6
● aca出现1次，其出现值为1=1：3=3
●bacab出现1次，其出现值为1：1：5=5
● abacaba出现1次，其出现值为1：1：7=7
故最大回文子串出现值为7。
【数据规模与评分】
数据满足1≤字符串长度≤300000。
实在很难0.0..
直接附上集训队作业zty的题解..
zty的题解
对着题解一顿乱敲..
听说这是回文自动机的裸题0.0（逃）
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int Maxn = 600010;
int F[Maxn], d[Maxn], ch[Maxn][26], tot, now;
int mx[Maxn], Rsort[Maxn], rk[Maxn], G[Maxn];
char s[Maxn]; int len;
bool v[Maxn];
int copy ( int p, int c ){int x = ++tot, y = ch[p][c];d[x] = d[p]+1;for ( int i = 0; i < 26; i ++ ) ch[x][i] = ch[y][i];F[x] = F[y]; F[y] = x;while ( ~p && ch[p][c] == y ){ ch[p][c] = x; p = F[p]; }return x;
}
void add ( int c ){int p, o;if ( p = ch[now][c] ){if ( d[p] != d[now]+1 ) copy ( now, c );now = ch[now][c];}else {d[o=++tot] = d[now]+1; p = now; now = o; G[o] = 1;while ( ~p && !ch[p][c] ){ ch[p][c] = o; p = F[p]; }F[o] = ~p ? ( d[p]+1 == d[ch[p][c]] ? ch[p][c] : copy ( p, c ) ) : 0;}
}
LL _max ( LL x, LL y ){ return x > y ? x : y; }
int main (){int i, j, k;scanf ( "%s", s+1 );len = strlen (s+1);F[0] = -1;for ( i = 1; i <= len; i ++ ){ add (s[i]-'a'); mx[now] = i; }for ( i = 1; i <= tot; i ++ ) Rsort[d[i]] ++;for ( i = 1; i <= len; i ++ ) Rsort[i] += Rsort[i-1];for ( i = tot; i >= 1; i -- ) rk[Rsort[d[i]]--] = i;for ( i = tot; i >= 1; i -- ){mx[F[rk[i]]] = _max ( mx[F[rk[i]]], mx[rk[i]] );G[F[rk[i]]] += G[rk[i]];}now = 0; int l = 0;LL ans = 0ll;memset ( v, false, sizeof (v) );for ( i = len; i >= 1; i -- ){int c = s[i]-'a';while ( ~now && !ch[now][c] ){ now = F[now]; l = d[now]; }if ( now < 0 ){ now = 0; l = 0; }else { now = ch[now][c]; l ++; }if ( mx[now] < i+l ){if ( mx[now] >= i ) ans = _max ( ans, (LL)G[now]*(mx[now]-i+1) );int p = now;while ( ~p && !v[p] ){if ( mx[p] < i+d[p] && i <= mx[p] ) ans = _max ( ans, (LL)G[p]*(mx[p]-i+1) );v[p] = true;p = F[p];}}}printf ( "%lld\n", ans );return 0;
}