记录编号	326296	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	Hzoi_Yniverse	是否通过	通过
代码语言	C++	运行时间	1.760 s
提交时间	2016-10-21 07:16:51	内存使用	50.61 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const long long maxn=1000010;
char s[maxn]; bool vis[maxn];
long long next[maxn],head[maxn],n,ans,k,len;
struct Edge{ long long to,next,dis; }e[maxn*2];
void Insert(long long x,long long y,long long z){
	len++;
	e[len].to=y; e[len].dis=z;
	e[len].next=head[x]; head[x]=len;
}
void GetNext(){
	next[1]=next[0]=0;
	long long j=0;
	for(long long i=1;i<n;i++){
		while(j&&s[i]!=s[j]) j=next[j];
		if(s[i]==s[j]) j++;
		next[i+1]=j;
	}
}
void Build(){
	for(long long i=1;i<=n;i++){
		long long z=(i-next[i])*(i-next[i]);
		Insert(i,next[i],z);
		Insert(next[i],i,z);
		//printf("i== next==%lld\n",i,next[i]);
	}
}
void Dfs(long long x,long long dis){
	//printf("x==%lld dis==%lld\n",x,dis); getchar();
	if(ans<=dis){ ans=dis; k=x; }
	for(long long i=head[x];i;i=e[i].next){
		long long j=e[i].to;
		if(!vis[j]){//printf("x==%lld j=%lld\n",x,j);
			vis[j]=1; Dfs(j,dis+e[i].dis);
		}
	}
}
int main(){
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	long long __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	scanf("%s",s); n=strlen(s);
	GetNext();
	Build();
	vis[0]=1; Dfs(0,0);
	memset(vis,0,sizeof(vis)); ans=0; //printf("k==%lld\n",k);
	vis[k]=1; Dfs(k,0);
	printf("%lld\n",ans);
	//while(1);
	return 0;
}