记录编号	326545	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	2.450 s
提交时间	2016-10-21 09:33:11	内存使用	22.59 MiB

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#define maxn 1000001
using namespace std;
typedef long long ll;
int n;
char ch[maxn];
void read(){
	scanf("%s",ch);
	n=strlen(ch);
	for (int i=n;i>=1;i--){
		ch[i]=ch[i-1];
	}
	ch[0]='_';
}
int next[maxn]={0};
class edge{
public:
	int from,to;
	ll dis;
};
vector<edge> G[maxn];
ll dist(int x,int y){
	return (ll)(y-x)*(ll)(y-x);
}
void make(){
	next[0]=next[1]=0;
	for (int i=2;i<=n;i++){
		int j=next[i-1];
		while(j){
			if (ch[i]==ch[j+1]){
				break;
			}
			else j=next[j];
		}
		if (ch[j+1]==ch[i]) next[i]=j+1;
		else next[i]=0;
//		printf("%d ",next[i]);
	}
	for (int i=1;i<=n;i++){
		int u=next[i],v=i;
		ll w=dist(next[i],i);
		G[u].push_back((edge){u,v,w});
		G[v].push_back((edge){v,u,w});
	}
}
ll d[maxn]={0};
bool vis[maxn]={0};
void dfs(int x,ll t){
	d[x]=t; vis[x]=1;
//	printf("%d\n",d[x]);
	for (int i=0;i<G[x].size();i++){
		edge e=G[x][i];
//		printf("%d %d\n",e.from,e.to);
		if (vis[e.to]) continue;
//			printf("	%d %d\n",e.from,e.to);
		dfs(e.to,d[x]+e.dis);
	}
}
void work(int s){
	memset(d,0,sizeof(d));
	memset(vis,0,sizeof(vis));
	dfs(s,0);
//	printf("\n");
}
int main(){
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	read();
	make();
	work(0);
	int s=0;
	for (int i=1;i<=n;i++){
		if (d[s]<d[i]) s=i;
//		printf("%d ",d[i]);
	}
//	printf("%d",s);
	work(s);
	ll ans=0;
	for (int i=0;i<=n;i++){
		ans=max(d[i],ans);
//		printf("%d ",d[i]);
	}
	printf("%lld",ans);
	return 0;
}