记录编号	379729	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[51nod 1129] 字符串最大值	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.572 s
提交时间	2017-03-07 14:59:12	内存使用	253.96 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=1000000*2;
struct SAM{
	int root,val;
	int next[26];
}a[maxn];
char s[maxn];
int RT,last,cnt;
int mp[maxn],num;
LL size[maxn];
void extend(int c){
	int p=last,np=++cnt;
	size[np]++;mp[num++]=np;
	a[np].val=a[p].val+1;
	while(p && !a[p].next[c]){
		a[p].next[c]=np;
		p=a[p].root;
	}
	if(!p)a[np].root=RT;
	else {
		int q=a[p].next[c];
		if(a[q].val==a[p].val+1)a[np].root=q;
		else {
			int nq=++cnt;a[nq]=a[q];
			a[nq].val=a[p].val+1;
			a[np].root=a[q].root=nq;
			while(p && a[p].next[c]==q){
				a[p].next[c]=nq;
				p=a[p].root;
			}
		}
	}last=np;
}
LL ans=0;
int Ws[maxn],Rank[maxn];
void Init();
int main(){
	freopen("string_maxval.in","r",stdin);freopen("string_maxval.out","w",stdout);
	Init();
	return 0;
}
inline void Init(){
	RT=last=++cnt;
	scanf("%s",s);
	int Length=strlen(s);
	for(int i=0;i<Length;i++)extend(s[i]-'a');

	for(int i=1;i<=cnt;i++) Ws[a[i].val]++;
	for(int i=1;i<=Length;i++)Ws[i]+=Ws[i-1];
	for(int i=cnt;i;i--) Rank[Ws[a[i].val]--]=i;
	for(int i=cnt;i;i--) {
		int now=Rank[i];
		size[a[now].root]+=size[now];
	}
	size[0]=size[1]=0;
	for(int i=0;i<Length;i++){
		ans=max(ans,1ll*size[mp[i]]*(i+1));
	}
	printf("%lld\n",ans);
}
/*
7
1 a
1 a
1 a
2 a
2 a
4 a
abcbacbacaaaaaaaaabacbacbacbabaaaaaaaaaaaaaaaaaaacbacbabcbacbacbbacb
 */