记录编号	326471	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	2.177 s
提交时间	2016-10-21 08:12:16	内存使用	87.83 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1000010
#define maxe 3000010
using namespace std;
typedef long long LL;
struct Edge{
	LL t,next;
	LL d;
}e[maxe];int len,head[maxe];
LL fall[maxn],size;
LL ans,dis[maxn];
char a[maxn];
void _addedge(LL x,int y,LL z){
	//printf("x=%d y=%d z=%lld\n",x,y,z);
	len++;
	e[len].t=y;
	e[len].d=z;
	e[len].next=head[x];
	head[x]=len;
}
void _mp(){
	fall[0]=fall[1]=0;
	LL p=0;
	for(LL i=1;i<size;i++){
		while(p&&a[p]!=a[i]) p=fall[p];
		if(a[p]==a[i])p++;
		fall[i+1]=p;
	}
	//for(LL i=0;i<=size;i++) printf("%d",fall[i]);
	for(LL i=0;i<=size;i++){
		LL x=i,y=fall[i],z=(fall[i]-i)*(fall[i]-i);
		_addedge(x,y,z); _addedge(y,x,z);
	}
		
}
bool vis[maxn];
void _dfs(LL x){
	vis[x]=1;
	for(LL i=head[x];i;i=e[i].next){
		LL y=e[i].t;
		if(!vis[y]){
			dis[y]=dis[x]+e[i].d;
			_dfs(y);
		}
	}
}
int main(){
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	scanf("%s",a);
	size=strlen(a);
	_mp();
	_dfs(1);
	LL p=0;
	LL Max=0ll;
	for(LL i=0;i<=size;i++){
		if(dis[i]>Max){
			Max=dis[i];
			p=i;
		}
	}
	memset(dis,0,sizeof dis);
	memset(vis,0,sizeof vis);
	_dfs(p);//printf("p==%d\n",p);
	Max=0ll;
	for(LL i=0;i<=size;i++){
		if(dis[i]>Max) Max=dis[i];
	}
	printf("%lld\n",Max);
	getchar();getchar();
	return 0;
}