自动搬运

查看原文

来自洛谷，原作者为

	行吟啸九州 成败总成空，功名谈笑中。岂如垂钓客，醉卧倚青松。

搬运于2025-08-24 22:40:44，当前版本为作者最后更新于2022-12-08 22:06:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述不是很清晰，实际上 $S$ 只由小写字母构成。

先说一下部分分做法，考虑二分，二分长度，利用 hash 和 map 来进行复杂度为 $O(n \log n)$ 的比较判断，总复杂度 $O(n \log ^ 2n)$。由于单 hash 的 hash 冲突比较严重，而双 hash 效率又太慢，故使用这个办法本人只获得了 $60$。

考虑使用 SAM 求出来所有子串的出现次数和长度，如果一个子串出现了 $2$ 次以上，则对答案进行一次贡献，复杂度 $O(n \log n)$。

#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define For(i, j, n) for(register int i = j ; i <= n ; ++i)
int ans, cnt, len, last;
int a[N], l[N], fa[N], go[N][26], siz[N];
string s;

inline void insert(int x){
	int p = last, np = ++cnt;
	last = np, siz[np] = 1, l[np] = l[p] + 1; 
	for( ; !go[p][x] && p ; p = fa[p]) go[p][x] = np;
	if(!p) return fa[np] = 1, void();
	int nq = go[p][x];
	if(l[nq] == l[p] + 1) fa[np] = nq;
	else{
		int q = ++cnt;
		fa[q] = fa[nq], fa[nq] = fa[np] = q;
		l[q] = l[p] + 1;
		memcpy(go[q], go[nq], sizeof(go[nq]));
		for( ; go[p][x] == nq ; p = fa[p]) go[p][x] = q;
	}
}

inline bool cmp(int x, int y){ return l[x] > l[y]; }
int main(){
    cin >> s, cnt = last = 1;
    for(auto i : s) insert(i - 'a');
    For(i, 1, cnt) a[i] = i;
	sort(a + 1, a + cnt + 1, cmp);
	For(i, 1, cnt){
		siz[fa[a[i]]] += siz[a[i]];
		if(siz[a[i]] > 1) ans = max(ans, l[a[i]]); 
	}
	printf("%d", ans);
	return 0;
}