http://www.lydsy.com/JudgeOnline/problem.php?id=3676
题意：给一个串求回文串×出现次数的最大值。（|S|<=300000）
#include <bits/stdc++.h>
using namespace std;
const int N=300005;
struct E {
int f[N], c[N][26], l[N], last, s[N], n, cnt[N], tot;
E() { f[0]=1; f[1]=0; l[1]=-1; n=0; s[0]=-1; tot=1; last=0; }
int find(int x) { while(s[n-l[x]-1]!=s[n]) x=f[x]; return x; }
void add(int ch) {
s[++n]=ch;
int x=find(last);
if(!c[x][ch]) {
int y=++tot;
f[y]=c[find(f[x])][ch];
c[x][ch]=y;
l[y]=l[x]+2;
}
cnt[last=c[x][ch]]++;
}
long long getans() {
for(int i=tot; i>=0; --i) cnt[f[i]]+=cnt[i];
long long ans=0;
for(int i=0; i<=tot; ++i) ans=max(ans, 1ll*cnt[i]*l[i]);
return ans;
}
}a;
char st[N], *s=st;
int main() {
scanf("%s", s);
for(; *s; ++s) a.add(*s-'a');
printf("%lld\n", a.getans());
return 0;
}
裸的回文自动机。。注意更新每个节点的时候是可以直接从后向前更新的。。（因为加点顺序本来就是拓扑序。。
