记录编号	538847	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[51nod 1129] 字符串最大值	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.783 s
提交时间	2019-07-31 18:21:16	内存使用	183.51 MiB

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+7+3e5+7;
int lst=1,tot=1,cnt;
LL ans;
int head[N],dp[N];
char s[N];
queue<int> que;
struct node
{
	int ch[26],fa,len;
} pt[N];
struct edge
{
	int nx,to;
} e[N<<1];
void extend(int c)
{
	int p=lst,np=lst=++tot;dp[np]=1;que.push(np);
	pt[np].len=pt[p].len+1;
	for (;p&&!pt[p].ch[c];p=pt[p].fa) pt[p].ch[c]=np;
	if (!p) pt[np].fa=1;
	else
	{
		int q=pt[p].ch[c];
		if (pt[q].len==pt[p].len+1) pt[np].fa=q;
		else
		{
			int nq=++tot;pt[nq]=pt[q];
			pt[nq].len=pt[p].len+1;
			pt[np].fa=pt[q].fa=nq;
			for (;!p&&pt[p].ch[c]==q;p=pt[p].fa) pt[p].ch[c]=nq;
		}
	}
}
void add_edge(int a,int b)
{
	cnt++;e[cnt].nx=head[a];e[cnt].to=b;head[a]=cnt;
}
void solve(int x)
{
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		solve(y);
		dp[x]+=dp[y];
	}
}
int main()
{
	freopen("string_maxval.in","r",stdin);
	freopen("string_maxval.out","w",stdout);
	//freopen("xxx.in","r",stdin);
	scanf("%s",s);int len=strlen(s);
	for (int i=0;i<len;i++) extend(s[i]-'a');
	for (int i=2;i<=tot;i++) add_edge(pt[i].fa,i);
	solve(1);
	while (!que.empty())
	{
		int pos=que.front();que.pop();
		ans=max(ans,(LL)pt[pos].len*dp[pos]);
	}
	printf("%lld\n",ans);
	return 0;
}