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

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
using namespace std;
int _read(){int ret,neg;char ch;ret=neg=0;while(!isdigit(ch=getchar())&&ch!='-');if(ch=='-')neg=1,ch=getchar();while(ret=ret*10+ch-'0',isdigit(ch=getchar()));if(neg)ret=-ret;return ret;}
const int maxn=1000005;
#define LL long long
char s[maxn];int n,head[maxn],len=1,next[maxn],vis[maxn],tim=0;LL dis[maxn];
struct _tree{int to,next;LL dis;}e[maxn<<1];
void _set(int prt,int son){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,
	e[len].dis=(LL)(son-prt)*(son-prt);
}
void _KMP(){
	n=strlen(s+1);int i,j=0;next[1]=0;
	for(i=2;i<=n;i++){
		while(j&&s[i]^s[j+1])j=next[j];
		if(s[i]==s[j+1])j++;
		next[i]=j;	
	}
	for(i=1;i<=n;i++)_set(next[i],i),_set(i,next[i]);
	//printf("%d ",next[i]);putchar('\n');
}
#define to e[i].to
queue<int>q;
void _run(int s){
//	for(int i=head[rt];i;i=e[i].next)
//		if(vis[to]^tim)vis[to]=tim,dis[to]=dis[rt]+e[i].dis,_run(to);
	while(!q.empty())q.pop();q.push(s);int rt,i;
	while(!q.empty()){
		rt=q.front(),q.pop();
		for(i=head[rt];i;i=e[i].next)
			if(vis[to]^tim)
				vis[to]=tim,dis[to]=(LL)dis[rt]+e[i].dis,q.push(to);
	}
}
void _work(){
	scanf("%s",s+1);_KMP();
	dis[1]=0,vis[1]=++tim;_run(1);int RT=0,i;LL ma=0;
	for(i=0;i<=n;i++)if(dis[i]>ma)ma=dis[i],RT=i;
	dis[RT]=0,vis[RT]=++tim;_run(RT);ma=0;
	for(i=0;i<=n;i++)if(dis[i]>ma)ma=dis[i];
	printf("%lld\n",ma);
}
bool _Rabit(),_RABIT=_Rabit();int main(){;}
bool _Rabit(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
#endif
	_work();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
}