Nowcoder Practice 61 E.相似的子串（Hash&二分)

题意：求给定字符串中相同但不相交的子串最大个数。

思路：二分查找子串长度，然后对每个长度从右端开始递推结果。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,mod=1e9+7;
typedef unsigned long long ull;
ull h[N],p[N]={1};
char s[N]; 
int n,k,ans;
bool fun(int len){
	 map<ull,pair<int,int> >mp;
	 for(int i=len;i<=n;i++){
	 	ull v=h[i]-h[i-len]*p[len];
	 	if(i-mp[v].first>=len) mp[v].first=i,mp[v].second++;//如果右端还有子串则更新右端和个数. 
	 	if(mp[v].second>=k) return 1;
	 }
	 return 0;
}
int main(){
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)//预处理 
		p[i]=p[i-1]*233,h[i]=h[i-1]*233+s[i];
	int l=1,r=n/k;
	while(l<=r){//二分查找最大值。 
		int mid=(l+r)>>1;
		if(fun(mid)) ans=mid,l=mid+1;
		else r=mid-1; 
	}
	printf("%d\n",ans);
	return 0;
}