记录编号	336564	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	dududu	是否通过	通过
代码语言	C++	运行时间	0.206 s
提交时间	2016-11-03 11:58:17	内存使用	14.87 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define LL long long
#define KN 1000010
char A[KN];
int N;
LL f[KN];
LL dp[KN];
void get_next(char *a,LL next[]){
	next[0]=-1;
	int i,j;
	for (i=1;a[i]!='\0';i++) {
        j=i-1;
        while (j>=0) {
            j=next[j];
            if (a[j+1]==a[i]){
                next[i]=j+1;
                j=0;
                break;
            }
        }
        if (j<0)
            next[i]=-1;
    }
}

void init(){
	
	scanf("%s",A);
	N=strlen(A);
	get_next(A,f);
}

void sol(){
	
	LL ans=0;
	LL empty_v=0;
	for(LL i=N-1;i>=0;i--){
		LL pos=f[i];
		if(pos!=-1){
			ans=max(ans,dp[i]+dp[pos]+(i-pos)*(i-pos));
			dp[pos]=max(dp[pos],dp[i]+(i-pos)*(i-pos));
		}else{
			ans=max(ans,empty_v+dp[i]+(i+1)*(i+1));
			empty_v=max(empty_v,dp[i]+(i+1)*(i+1));
		}
	}
	printf("%lld",ans);
}

void test(){
	
	for(int i=0;i<N;i++) printf("%d ",f[i]);
	printf("\n");
	
}
int main(){
	freopen("savemzx.in", "r", stdin);
	freopen("savemzx.out", "w", stdout);
	init();
//	test();
	sol();
	return 0;
}