【BZOJ】3676: [Apio2014]回文串

#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;
}