萌新求助,全WA
查看原帖
萌新求助,全WA
165375
Fast_Gai_Tle楼主2021/7/6 16:06
#include <bits/stdc++.h>
#define N 1000005
#define re register
using namespace std;
typedef long long ll;

char s[N];
int L;
int t[2*N];
struct SAM{
	int las, tot;
	int edge[2*N][26], fa[2*N], len[2*N], id[2*N], sz[2*N];
	SAM(){ las = tot = 1; memset(edge, 0, sizeof(edge)); memset(fa, 0, sizeof(fa)); }
	void add(int c){
		int p = las, np = las = ++tot;
		len[np] = len[p] + 1; sz[np] = 1;
		for(; p && !edge[p][c]; p = fa[p]) edge[p][c] = np;
		if(!p){ fa[np] = 1; return ; }
		int q = edge[p][c];
		if(len[q] == len[p] + 1){ fa[np] = q; return ; }
		int nq = ++tot;
		memcpy(edge[nq], edge[q], sizeof(edge[nq]));
		len[nq] = len[p] + 1; fa[q] = fa[np] = nq; sz[nq] = 0;
		for(; p && edge[p][c] == q; p = fa[p]) edge[p][c] = nq;
	}
	void _sort(){
		memset(t, 0, sizeof(t));
		for(re int i = 1; i <= tot; ++i) ++t[len[i]];
		for(re int i = 1; i <= tot; ++i) t[i] += t[i - 1];
		for(re int i = 1; i <= tot; ++i) id[t[len[i]]--] = i;
	}
}S;

void init(){
	scanf("%s", s); L = strlen(s);
	for(re int i = 0; i < L; ++i)
		S.add(s[i] - 'a');
}

ll ans;
void solve(){
	S._sort();
	for(re int i = S.tot; i >= 1; --i){
		int now = S.id[i]; S.sz[S.fa[now]] += S.sz[now];
		if(S.sz[now] > 1) ans = max(ans, 1LL * S.sz[now] * S.len[now]);
	}
	printf("%lld\n", ans);
}

int main(){
	init();
	solve();
	return 0;
}
2021/7/6 16:06
加载中...