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

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
using i64 = long long;
using u64 = unsigned long long;
using pii = std::pair<int,int>;

const int maxn = 1e6 + 5;
int n,m,rk[maxn << 1],oldrk[maxn << 1],rkid[maxn],height[maxn],sa[maxn],cnt[maxn],id[maxn];
char s[maxn];
i64 ans;

bool cmp(int x,int y,int w) {
	return oldrk[x] == oldrk[y]&&oldrk[x + w] == oldrk[y + w];
}

int pre[maxn],sz[maxn];

int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

void merge(int x,int y,int z) {
	x = find(x);
	y = find(y);
	if(x == y)return ;
	if(sz[x] > sz[y])
		std::swap(x , y);
	pre[x] = y;
	sz[y] += sz[x];
	ans = std::max(ans , 1ll * sz[y] * z);
	return ;
}

int main() {
	freopen("string_maxval.in","r",stdin);
	freopen("string_maxval.out","w",stdout);
	scanf("%s",s + 1);
	ans = n = strlen(s + 1);
	m = 300;
	for(int i = 1;i <= n;++ i)
		++ cnt[rk[i] = s[i]];
	for(int i = 1;i <= m;++ i)
		cnt[i] += cnt[i - 1];
	for(int i = n;i >= 1;-- i)
		sa[cnt[rk[i]] --] = i;
	for(int w = 1;w < n;w <<= 1) {
		int p = 0;
		for(int i = n;i > n - w;-- i)
			id[++ p] = i;
		for(int i = 1;i <= n;++ i)
			if(sa[i] > w)
				id[++ p] = sa[i] - w;
		for(int i = 1;i <= m;++ i)
			cnt[i] = 0;
		for(int i = 1;i <= n;++ i)
			++ cnt[rkid[i] = rk[id[i]]];
		for(int i = 1;i <= m;++ i)
			cnt[i] += cnt[i - 1];
		for(int i = n;i >= 1;-- i)
			sa[cnt[rkid[i]] --] = id[i];
		std::swap(rk , oldrk);
		m = 0;
		for(int i = 1;i <= n;++ i)
			rk[sa[i]] = (m += !cmp(sa[i] , sa[i - 1] , w));
		if(m >= n)
			break ;
	}
	for(int i = 1;i <= n;++ i)
		rk[sa[i]] = i;
	for(int i = 1,k = 0;i <= n;++ i) {
		if(rk[i] == 1)
			k = 0;
		else {
			if(k > 0)
				-- k;
			int j = sa[rk[i] - 1];
			while(i + k <= n&&j + k <= n&&s[i + k] == s[j + k])
				++ k;
		}
		height[rk[i]] = k;
	}
	for(int i = 1;i <= n;++ i)
		pre[i] = id[i] = i,sz[i] = 1;
	std::sort(id + 2 , id + 1 + n , [&](const int& p,const int& q) {
		return height[p] > height[q];
	});
	for(int i = 2;i <= n;++ i) {
		merge(sa[id[i] - 1] , sa[id[i]] , height[id[i]]);
	}
	printf("%lld\n",ans);
	return 0;
}