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

/*
	Name: 拯救紫萱学姐
	Copyright: 
	Author: chairman
	Date: 21/10/16 07:14
	Description: kmp求前缀，然后，以前缀为父亲建树，找树的直径 
*/
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define ll long long
int read()
{
    int x,f=1;
    char ch;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
    x=ch-48;
    while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
    return x*f;
}
void write(ll x)
{
	if(x<0)putchar('-'),x=-x;
	int cnt=0;char ch[50];
	while(ch[++cnt]=x%10+48,x/=10);
	while(putchar(ch[cnt]),--cnt);
	putchar('\n');
}
#define maxe 2001000
#define maxn 2001000
struct edge
{
	int t,n;ll d;
}a[maxe];
int len,head[maxn],fa[maxn],cnt=1,D,f[maxn],goal;ll ans=0;
void insert(int x,int y,ll z)
{
	a[++len].t=y;a[len].d=z;a[len].n=head[x];head[x]=len;
}
#define k a[i].t
void dfs(int x,ll now)
{
	for(int i=head[x];i;i=a[i].n)
	{
		if(fa[x]==k)continue;
		fa[k]=x;
		dfs(k,now+a[i].d);
		if(now+a[i].d>ans)ans=now+a[i].d,goal=k;
	}
}
#undef k
int main()
{
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	string s;
	cin>>s;
	int n=s.length();
	for(int i=1;i<n;i++)
	{
		int j=f[i];
		while(j&&s[j]!=s[i])j=f[j];
		if(s[j]==s[i])f[i+1]=j+1;
		else f[i+1]=0;
	}
	for(int i=0;i<n;i++)
	{
		int x=f[i+1];
		if(!x)insert(n+1,i+1,1LL*(i+1)*(i+1)),insert(i+1,n+1,1LL*(i+1)*(i+1));
		else
		{//因为是前缀，肯定已经处理过了 
			insert(x,i+1,1LL*(i+1-x)*(i+1-x));insert(i+1,x,1LL*(i+1-x)*(i+1-x));
		}
	}
	dfs(n+1,0);
	memset(fa,0,sizeof fa);ans=0;
	dfs(goal,0);
	write(ans);
//	system("pause");
	fclose(stdin);
	fclose(stdout);
}