记录编号	395317	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2014] Palindromes	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.058 s
提交时间	2017-04-15 16:05:36	内存使用	5.98 MiB

#include<cstring>
#include<cstdio>
#include<iostream>
#define N 300010
typedef long long LL;
using namespace std;

int len,i;
LL Ans;
char c[N];

inline LL Max(LL a,LL b){return (a>b)?a:b;}

struct P_Tree{
	int n,tot,last;
	int cnt[N],fail[N],ch[N][26],l[N],s[N];
	
	inline int NewNode(int x){
		l[tot]=x;	return tot++;
	}
	
	inline void Ready(){
		s[0]=-1;	fail[0]=1;
		NewNode(0);	NewNode(-1);
	}
	
	inline int Getfail(int x){
		while (s[n-l[x]-1]!=s[n])	x=fail[x];
		return x;
	}
	
	inline void Add(int C){
		int cur=0,now=0;
		C-=96;	s[++n]=C;
		cur=Getfail(last);
		if (!ch[cur][C]){
			now=NewNode(l[cur]+2);
			fail[now]=ch[Getfail(fail[cur])][C];
			ch[cur][C]=now;
		}
		cnt[last=ch[cur][C]]++;
	}
	
	inline void Count(){
		for (int i=tot-1;i>=0;i--)	cnt[fail[i]]+=cnt[i];
		for (int i=2;i<tot;i++)	Ans=Max(Ans,1ll*l[i]*cnt[i]);
	}
}PAM;

int main(){
	freopen("apio2014_palindrome.in","r",stdin);
	freopen("apio2014_palindrome.out","w",stdout);
	scanf("%s",&c);	len=strlen(c)-1;
	PAM.Ready();
	for (i=0;i<=len;i++)	PAM.Add(c[i]);
	PAM.Count();
	printf("%lld\n",Ans);
	return 0;
}