记录编号	360743	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2014] Palindromes	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.519 s
提交时间	2016-12-31 18:56:28	内存使用	67.24 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6e5+10;
char s[N];
int n,top,last,len[N],par[N],go[N][26],cnt[N];
int New(int L){len[top]=L;return top++;}
void extend(int n){
	int p=last,w=s[n];
	while (w!=s[n-len[p]-1]) p=par[p];
	if (!go[p][w]){
		int q=New(len[p]+2),now=p;
		do p=par[p];while (w!=s[n-len[p]-1]);
		par[q]=go[p][w];
		last=go[now][w]=q;
	}
	else last=go[p][w];
	cnt[last]++;
}
int main()
{
	freopen("apio2014_palindrome.in","r",stdin);
	freopen("apio2014_palindrome.out","w",stdout);
	last=New(0);New(-1);par[0]=1;
	scanf("%s",s+1);
	s[0]=-1;
	n=strlen(s+1);
	for (int i=1;i<=n;i++) s[i]-='a';
	for (int i=1;i<=n;i++) extend(i);
	long long ans=0;
	for (int i=top-1;i>=0;i--){
		cnt[par[i]]+=cnt[i];
		ans=max(ans,1ll*cnt[i]*len[i]);
	}
	printf("%lld\n",ans);
	return 0;
}