记录编号	326320	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	2.276 s
提交时间	2016-10-21 07:21:18	内存使用	63.26 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <deque>
#include <ctime>
#define Mem(a,v) memset(a,v,sizeof(a))
using namespace std;
/*
freopen(".in","r",stdin);
	freopen(".out","w",stdout);
getchar(); getchar();
	return 0;
*/
typedef long long LL;
#define maxn 1000010

LL N,Next[maxn],len,head[maxn];
char s[maxn];
struct Edge
{
	LL to,next; LL dis;	
}e[maxn << 1];
void insert(LL x,LL y,LL z){
	e[++len].to = y; e[len].dis = z;
	e[len].next = head[x]; head[x] = len;	
}
void Get_Next(){
	Next[0] = Next[1] = 0;
	LL j = 0;
	for(LL i = 1;i < N;i ++){
		while(j && s[i]!=s[j]) j = Next[j];	
		if(s[i] == s[j]) j ++ ;
		Next[i+1] = j;
	}	
	/*
	for(LL i=1;i<=N;i++){
		printf("%d",Next[i]);	
	}*/
}
LL DIS(LL s,LL t){
	return (LL)((s - t)*(s - t));
}
void Build_Edge(){
	for(LL i=1;i<=N;i++){
		LL to = Next[i];
		insert(i,to,DIS(i,to));
		insert(to,i,DIS(to,i));	
		//printf("i = %d to = %d  dis = %d\n",i,to,DIS(i,to));
	}
}
bool vis[maxn];
LL ans1,ans;
LL Max1,Max;
void Dfs(LL x,LL dis){
	vis[x] = 1;
	for(LL i = head[x]; i ; i = e[i].next){
		LL p = e[i].to;
		if(!vis[p]){
			LL tdis = dis + e[i].dis;
			if(tdis > Max){
				Max = tdis; ans = p;
			}	
			Dfs(p,tdis);
		}
	}
}
int main(){
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	
	LL __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	
	scanf("%s",s);
	N = strlen(s);
	Get_Next();	
	Build_Edge();
	Dfs(0,0);
	ans1 = ans; Max1 = Max;
	ans = 0; Max = 0;
	Mem(vis,0);
	Dfs(ans1,0);
	printf("%lld\n",max(Max,Max1));
	
	//printf("clock = %d\n",clock());
	getchar(); getchar();
	return 0;
}