记录编号	284139	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2014] Palindromes	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.603 s
提交时间	2016-07-17 08:32:36	内存使用	35.86 MiB

# define maxc 26ul
# define maxn 300010ul

# include <stdio.h>
# include <string.h>
# include <algorithm>

struct node {
	node *ch[maxc],*fail;
	int len,v,id;
} *now,*root[2],*pre[maxn],spT[maxn];

char s[maxn]; int n,tot,N; long long ans=1;

void prepare() {
	root[0]=&spT[N=0];
	root[0]->id=N;
	root[1]=&spT[++N];
	root[1]->id=N;
	now=root[1];
	root[0]->fail=root[1]->fail=root[0];
	root[0]->len=-1,root[1]->len=0;
	n=0,tot=0; s[n++]=-1; return;
}

node* new_node(int x) {
	node *tmp=&spT[++N];
	tmp->id=N,pre[N]=tmp;
	tmp->len=x; return tmp;
}

node* get(node *p) {
	while(s[n-p->len-2]!=s[n-1])
		p=p->fail;
	return p;
}

void add(char c) {
	int t=c-'a'; s[n++]=c;
	node *p=get(now);
	if(p->ch[t]==NULL) {
		now=new_node(p->len+2);
		if(now->len==1) now->fail=root[1];
		else now->fail=get(p->fail)->ch[t];
		p->ch[t]=now,++tot;
	} now=p->ch[t],++now->v; return;
}

void count() {
	for(int i=N;i>=2;--i) {
		node *tmp=pre[i];
		if(tmp->fail) tmp->fail->v+=tmp->v;
		ans=std::max(ans,1ll*tmp->v*tmp->len);
	} return;
}

char str[maxn];

int main() {
	freopen("apio2014_palindrome.in","r",stdin);
	freopen("apio2014_palindrome.out","w",stdout);
	prepare(); scanf("%s",str); int len=strlen(str);
	for(int i=0;i<len;i++) add(str[i]);
	count(); printf("%lld\n",ans);
	return 0;
}