记录编号	327096	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	gls1196	是否通过	通过
代码语言	C++	运行时间	2.337 s
提交时间	2016-10-21 19:46:03	内存使用	64.21 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=1000100;
char str[maxn];
ll nxt[maxn],n,he[maxn],ed=0,dis[maxn],q[maxn];
bool vis[maxn];
struct Edge{
	ll v,nx,w;
	Edge(ll x,ll y,ll z){
		v=x;nx=y;w=z;
	}
	Edge(){;}
}e[maxn<<1];
void Add(ll u,ll v,ll w){
	e[++ed]=Edge(v,he[u],w);he[u]=ed;
}
void Gnxt(){ll i,j;
	for(i=2;str[i]!='\0';i++){
		j=nxt[i-1];
		while(j&&str[j+1]!=str[i])j=nxt[j];
		if(str[j+1]==str[i])j++;
		nxt[i]=j;
	}
}
ll Bfs(int st){int h=0,t=0;
	memset(vis,0,sizeof(vis));
	dis[st]=0;vis[st]=1;q[++t]=st;
	while(h<t){
		ll u=q[++h];
		for(ll i=he[u];i;i=e[i].nx){
			ll v=e[i].v;
			if(vis[v])continue;
			dis[v]=dis[u]+e[i].w;
			q[++t]=v;vis[v]=1;
		}
	}ll res=0;
	for(ll i=1;i<=n;i++)
		if(dis[res]<dis[i])res=i;return res;
}
int main(){
	 freopen("savemzx.in","r",stdin);
    freopen("savemzx.out","w",stdout);
	scanf("%s",str+1);n=strlen(str+1);Gnxt();
	for(ll i=1;i<=n;i++){
		Add(nxt[i],i,(i-nxt[i])*(i-nxt[i]));
		Add(i,nxt[i],(i-nxt[i])*(i-nxt[i]));
	}ll res=Bfs(Bfs(0));
	printf("%lld",dis[res]);
}