记录编号	479053	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[51nod 1129] 字符串最大值	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.461 s
提交时间	2017-12-15 23:02:01	内存使用	246.36 MiB

#include<bits/stdc++.h>
#define MAXN 2000010
using namespace std;
int S,tot,np,r[MAXN],t[MAXN][27],len[MAXN],f[MAXN];
void Insert(int x){
	int p=np;len[np=++tot]=len[p]+1;r[np]=1;
	while(p&&!t[p][x])t[p][x]=np,p=f[p];
	if(!p){f[np]=S;return;}
	int q=t[p][x];
	if(len[q]==len[p]+1)f[np]=q;
	else{
		int nq=++tot;
		memcpy(t[nq],t[q],sizeof(t[q]));
		f[nq]=f[q];len[nq]=len[p]+1;
		f[q]=f[np]=nq;
		while(p&&t[p][x]==q)t[p][x]=nq,p=f[p];
	}
}
int n,sum[MAXN],id[MAXN],ans;
char ch[MAXN];
int main(){
	freopen("string_maxval.in","r",stdin);
	freopen("string_maxval.out","w",stdout);
	scanf("%s",ch);
	n=strlen(ch);
	S=np=tot=1;
	for(int i=0;i<n;i++)Insert(ch[i]-'a');
	for(int i=1;i<=tot;i++)sum[len[i]]++;
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
	for(int i=1;i<=tot;i++)id[sum[len[i]]--]=i;
	for(int i=tot;i;i--)r[f[id[i]]]+=r[id[i]];
	for(int i=1;i<=tot;i++)ans=max(ans,r[i]*len[i]);
	printf("%d",ans);
	return 0;
}