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

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=1001000;
char ch[maxn];
LL f[maxn],n,len,flag[maxn],cnt,head[maxn],ma,dis[maxn],maa;
struct Edge
{
	LL to,next,dis;
}e[maxn*2];
void getfail();
void Insert(LL,LL,LL);
void Dfs(LL);
int main()
{
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	int __size__=100<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	memset(head,-1,sizeof(head));
	scanf("%s",ch);getfail();
	//for(int i=1;i<=n;i++)printf("%d ",f[i]);
	cnt++;ma=-0x7f7f7f7f;Dfs(0);
	memset(dis,-0x7f,sizeof(dis));//printf("tem==%d\n",maa);
	cnt++;ma=-0x7f7f7f7f;
	dis[maa]=0;Dfs(maa);
	printf("%lld\n",ma);
	fclose(stdin);
	fclose(stdout);
	//system("pause");
	return 0;
}
void getfail()
{
	n=strlen(ch);Insert(1,0,1);Insert(0,1,1);
	for(int i=1;i<n;i++)
	{
		LL j=f[i];
		while(j&&ch[i]!=ch[j])j=f[j];
		if(ch[i]==ch[j]){f[i+1]=j+1;Insert(j+1,i+1,(i-j)*(i-j));Insert(i+1,j+1,(i-j)*(i-j));}
		else {f[i+1]=0;Insert(0,i+1,(i+1)*(i+1));Insert(i+1,0,(i+1)*(i+1));}
	}
}
void Dfs(LL x)
{
	if(dis[x]>ma){ma=dis[x];maa=x;}
	flag[x]=cnt;//printf("%d\n",x);
	for(int i=head[x];i!=-1;i=e[i].next)
	{
		LL j=e[i].to;
		if(flag[j]!=cnt)
		{
			dis[j]=dis[x]+e[i].dis;
			Dfs(j);
		}
	}
}
void Insert(LL x,LL y,LL z)
{
	len++;e[len].to=y;e[len].next=head[x];
	head[x]=len;e[len].dis=z;
}
/*
求最长链，先随机找一个点，搜离这个点最远的点
再从这个点找一个最远的点，即为树的直径 
*/