记录编号	326467	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	派特三石	是否通过	通过
代码语言	C++	运行时间	1.804 s
提交时间	2016-10-21 08:10:27	内存使用	49.95 MiB

/*
	Name: 
	Copyright: 
	Author: 
	Date: 21/10/16 08:08
	Description: 每个前缀和它的相似前缀建边，以每个前缀做结点，构成一棵树，找树的直径。
	思想来源于跳跳棋。 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define pa system("pause")
using namespace std;
const int maxn=1001000;
typedef long long LL;
string s,ss;
struct edge
{
 	int from,to,next;LL dis;
}e[maxn<<1];
int n,m,len,head[maxn],flag[maxn],tot,ans,f[maxn],Time;LL temp,ma;
void insert(int x,int y,LL z)
{
	e[++len].from=x;e[len].to=y;e[len].dis=z;e[len].next=head[x];head[x]=len;
}
void MP()
{
	f[0]=f[1]=0;
	int len=s.size();
	for(int i=1;i<len;++i)
	{
		int j=f[i];
		while(j&&s[i]!=s[j])j=f[j];
		if(s[i]==s[j])f[i+1]=j+1;
		else f[i+1]=0;
	}
	for(int i=1;i<=len;++i)
	{
		insert(i,f[i],(LL)(i-f[i])*(i-f[i]));
		insert(f[i],i,(LL)(i-f[i])*(i-f[i]));
	}
}
void dfs(int x,LL tot)
{
	flag[x]=Time;
	for(int i=head[x];i;i=e[i].next)
	{
		int k=e[i].to;
		if(flag[k]==Time)continue;
		if(tot+e[i].dis>ma)
		{
			ma=tot+e[i].dis;
			temp=k;
		}
		flag[k]=Time;
		dfs(k,tot+e[i].dis);
	}
}
int main()
{
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	cin>>s;
	MP();Time++;
	dfs(0,0);Time++;
	dfs(temp,0);
	printf("%lld\n",ma);
}