Description
考虑一个只包含小写拉丁字母的字符串\(s\)。我们定义\(s\)的一个子串\(t\)的“出现值”为\(t\)在\(s\)中的出现次数乘以\(t\)的长度。请你求出\(s\)的所有回文子串中的最大出现值。
Input
输入只有一行，为一个只包含小写字母a-z的非空字符串\(s\)。
Output
输出一个整数，为所有回文子串的最大出现值。
Sample Input1
abacaba
Sample Input2
www
Sample Output1
7
Sample Output2
4
HINT
\(1 \le \mid s \mid \le300000\)
朴素做法：manacher+后缀数组。用manacher求出所有本质不同的回文串，对于每个本质不同的回文串，在后缀数组中二分出它的出现次数。复杂度\(O(nlogn)\)。（参见ZJOI模拟题BYcenbo palindrome）
但是我们有回文自动机（参见：Palindromic Tree——回文树【处理一类回文串问题的强力工具】）。你知道回文自动机能做什么，你就能AC了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long ll;
#define maxn (300010)
ll ans;
struct pat
{
int next[maxn][26],fail[maxn],cnt[maxn],len[maxn],s[maxn],last,n,p;
inline int newnode(int l) { cnt[p] = 0; len[p] = l; return p++; }
inline void init() { last = n = p = 0; newnode(0); newnode(-1); s[0] = -1; fail[0] = 1; }
inline int getfail(int x) { while (s[n-len[x]-1] != s[n]) x = fail[x]; return x; }
inline void add(int c)
{
s[++n] = c; int cur = getfail(last);
if (!next[cur][c])
{
int now = newnode(len[cur]+2);
fail[now] = next[getfail(fail[cur])][c];
next[cur][c] = now;
}
last = next[cur][c]; cnt[last]++;
}
inline void count()
{
for (int i = p-1;i >= 0;--i) cnt[fail[i]] += cnt[i];
for (int i = 0;i < p;++i) ans = max(ans,(ll)cnt[i]*len[i]);
}
}tree;
int main()
{
freopen("3676.in","r",stdin);
freopen("3676.out","w",stdout);
tree.init();
while (true)
{
char ch = getchar();
if (ch >= 'a'&&ch <= 'z') tree.add(ch-'a');
else break;
}
tree.count(); printf("%lld",ans);
fclose(stdin); fclose(stdout);
return 0;
}