记录编号	478985	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2014] Palindromes	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.460 s
提交时间	2017-12-15 14:00:42	内存使用	38.34 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300010;
struct PAM{
	char s[maxn];
	int ch[maxn][30],fail[maxn],cnt[maxn],len[maxn],last,now,p;
	long long ans;
	void newnode(int w){
		cnt[now]=0,len[now]=w,now++;
	}
	void init(){
		now=0,newnode(0),newnode(-1);
		last=p=0,s[0]=-1,fail[0]=1;
	}
	int getfail(int x){
		while(s[p-len[x]-1]!=s[p])x=fail[x];
		return x;
	}
	void extend(int x){
		p++;
		int cur=getfail(last);
		if(!ch[cur][x]){
			newnode(len[cur]+2);
			fail[now-1]=ch[getfail(fail[cur])][x];
			ch[cur][x]=now-1;
		}
		last=ch[cur][x];
		cnt[last]++;
	}
	long long count(){
		ans=0;
		for(int i=now-1;i>=0;i--)cnt[fail[i]]+=cnt[i],ans=max(ans,(long long)len[i]*cnt[i]);
		return ans;
	}
}pam;
int main(){
	freopen("apio2014_palindrome.in","r",stdin);
	freopen("apio2014_palindrome.out","w",stdout);
	pam.init();
	scanf("%s",pam.s+1);
	int l=strlen(pam.s+1);
	for(int i=1;i<=l;i++)pam.extend(pam.s[i]-'a');
	printf("%lld\n",pam.count());
	return 0;
}