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

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define ull unsigned long long
using namespace std;
int n,cnt;ll ans;
struct node{int to,next;ll val;}e[5010000];
char s[1001000];
ll   f[1001000];
ll   dis[1001000];
int head[1001000];
ll calc(int x,int y){return (ll)(y-x)*(ll)(y-x);}
void add(int u,int v)
{
   ++cnt;
   e[cnt].to=v;
   e[cnt].val=calc(u,v);
   e[cnt].next=head[u];
   head[u]=cnt;
}
void get()
{
  f[0]=0,f[1]=0;
  for(int i=2;i<=n;i++)
  {
	  int j=f[i-1];
	  while(j&&s[i]!=s[j+1])j=f[j];
	  f[i]= s[i]==s[j+1]?j+1:0;
	  ans=max(ans,calc(i,f[i]));
  }
}
void dfs(int rt,int fa)
{
     for(int i=head[rt];i;i=e[i].next)
     {
	     int to=e[i].to;
	     if(to==fa)continue;
	     dis[to]=dis[rt]+e[i].val;
	     dfs(to,rt);
     }
}
void work1()
{
   for(int i=1;i<=n;i++)
   add(i,f[i]),add(f[i],i);
   dfs(0,-1);
   int mn;ll mx=0;
   for(int i=0;i<=n;i++)
	   if(mx<dis[i])
		   mn=i,mx=dis[i];
   memset(dis,0,sizeof(dis));
   dfs(mn,-1);
   mx=0;
   for(int i=0;i<=n;i++)
	   if(mx<dis[i])
		   mn=i,mx=dis[i];
   cout<<mx<<endl;
}
int main()
{
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
   	scanf("%s",s+1);n=strlen(s+1);
	get();work1();
}