自动搬运

查看原文

来自洛谷，原作者为

	Clare613 csacademy.com||宣:https://www.luogu.com.cn/team/103922||250粉后橙名就别找我了||目标一：黄+绿+蓝+紫+黑->431/888||目标二：2025J：320+，2025S:250+||个人题库已满

搬运于2025-08-24 22:20:57，当前版本为作者最后更新于2025-07-20 21:38:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路：

这是打 OI 比赛时场切的，写篇题解纪念一下。
第一步，审题。看到这样的题面，判断是哈希。然后看数据范围：$1\le L\le 2\times 10^5$，判断是哈希 + 二分。
很快把哈希板子打出来，然后写 $\operatorname{check}$ 函数。不难发现，unordered_map<int,bool> 叠加 O2 优化后不会超时。于是就可以利用 unordered_map<int,bool> 秒了这道题。
⚠⚠⚠注意事项：不同的位置不代表不重叠，请注意。

code：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int ha[200005],pw[200005];
unordered_map<int,bool> f;
int n;
string x;
int hashh(int l,int r){
	return ha[r]-ha[l-1]*pw[r-l+1];
}
bool check(int x){
	f.clear();
	for(int i=x;i<=n;i++){
		if(f[hashh(i-x+1,i)]==1){
			return 1;
		}
		f[hashh(i-x+1,i)]=1;
	}
	return 0;
}
signed main(){
	cin>>n;
	cin>>x;
	x=" "+x;
	pw[0]=1;
	for(int i=1;i<=n;i++){
		ha[i]=ha[i-1]*13331+x[i];
		pw[i]=pw[i-1]*13331;
	}
	int l=0,r=n;
	while(l<r){
//		cout<<l<<" "<<r<<"\n";
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid;
		else r=mid-1; 
	}
	cout<<l;
	return 0;
}