记录编号	341294	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	0.176 s
提交时间	2016-11-07 16:18:59	内存使用	11.44 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1000000+10; 
char A[maxn];
int p[maxn]={0};
long long f[maxn]={0};
long long ans=0,res=0;
int main(){
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	scanf("%s",A+1);
	int len=strlen(A+1);
	int j=0;
	for(int i=2;i<=len;i++){
		while(j&&A[j+1]!=A[i])
			j=p[j];
		if(A[j+1]==A[i])
			j++;
		p[i]=j;
	}
	for(int i=len;i;i--){
		int t=p[i];
		if(t){
			ans=max(ans,f[t]+f[i]+(long long)(i-t)*(i-t));
			f[t]=max(f[t],f[i]+(long long)(i-t)*(i-t));
		}
		else {
			ans=max(ans,res+i*i+f[i]);
			res=max(res,i*i+f[i]);
		}
	}
	printf("%lld\n",ans);
return 0;
}