C++(g++ 7.5.0) 解法, 执行用时: 1016ms, 内存消耗: 313416K, 提交时间: 2023-04-15 16:44:11

#include <bits/stdc++.h>

using namespace std;
//#define map unordered_map
//#define int long long
const int N = 1e6 + 10;
typedef long long ll;
char s[N];

int tot = 1, np = 1;
int fa[N << 1], ch[N << 1][26], len[N << 1];
ll cnt[N << 1], ans;
vector<int> g[N << 1];

void extend(int c) {
	int p = np;
	np = ++tot;
	len[np] = len[p] + 1, cnt[np] = 1;

	while (p && !ch[p][c]) {
		ch[p][c] = np;
		p = fa[p];
	}

	if (!p) {
		fa[np] = 1;
	}
	else {
		int q = ch[p][c];
		if (len[q] == len[p] + 1) fa[np] = q;
		else {
			int nq = ++tot;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q], fa[q] = fa[np] = nq;

			while (p && ch[p][c] == q) {
				ch[p][c] = nq;
				p = fa[p];
			}
			memcpy(ch[nq], ch[q], sizeof ch[q]);
		}
	}
}

void dfs(int u) {
	for (auto v : g[u]) {
		dfs(v);
		cnt[u] += cnt[v];
	}
	if (cnt[u] > 1) ans = max(ans, cnt[u] * len[u]);
}

signed main()
{
	scanf("%s", s);
	for (int i = 0; s[i]; ++i) {
		extend(s[i] - 'a');
	}
	for (int i = 2; i <= tot; ++i) {
		g[fa[i]].push_back(i);
	}
	dfs(1);
	cout << ans << '\n';

	return 0;
}

C++ 解法, 执行用时: 324ms, 内存消耗: 241600K, 提交时间: 2022-07-27 12:35:09

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
char s[N];
int a[N],c[N],siz[N];
int last,cnt;
int ch[N<<1][26],fa[N<<1],len[N<<1];
void extend(int C)
{
	int p=last,np=++cnt;
	last=np;
	len[np]=len[p]+1;
	for(;p&&!ch[p][C];p=fa[p])ch[p][C]=np;
	if(!p)fa[np]=1;
	else
	{
		int q=ch[p][C];
		if(len[p]+1==len[q])fa[np]=q;
		else
		{
			int nq=++cnt;
			len[nq]=len[p]+1;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			for(;ch[p][C]==q;p=fa[p])ch[p][C]=nq;
		}
	}
	siz[np]=1;
}
void build()
{
	for(int i=1;i<=cnt;i++)c[len[i]]++;
	for(int i=1;i<=cnt;i++)c[i]+=c[i-1];
	for(int i=1;i<=cnt;i++)a[c[len[i]]--]=i;
	for(int i=cnt;i;i--){int p=a[i];siz[fa[p]]+=siz[p];}
}
void solve()
{
	long long ans=0;
	for(int i=1;i<=cnt;i++)if(siz[i]!=1)
		ans=max(ans,1ll*len[i]*siz[i]);
	printf("%lld\n",ans);
}
int main()
{
	scanf("%s",s+1);
	int Len=strlen(s+1);
	last=cnt=1;
	for(int i=1;i<=Len;i++)extend(s[i]-'a');
	build();
	solve();
	return 0;
}