C++14(g++5.4) 解法, 执行用时: 1347ms, 内存消耗: 16196K, 提交时间: 2020-04-11 14:10:29

#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;
}

C++(clang++ 11.0.1) 解法, 执行用时: 710ms, 内存消耗: 16276K, 提交时间: 2022-11-02 09:54:15

#include<bits/stdc++.h>
using namespace std;
char s[1000001];
long long n,m,k,ans,ha[1000001],p[1000001];
inline bool check(long long x){
	map<long long,pair<long long,long long> >mp;
	for(int i=x;i<=n;++i){
		long long tmp=ha[i]-ha[i-x]*p[x];
		if(i-mp[tmp].first>=x)mp[tmp].first=i,mp[tmp].second++;
		if(mp[tmp].second>=k)return true;
	}
	return false;
}
int main(){
	cin>>n>>k>>s+1;p[0]=1;
	for(int i=1;i<=n;++i)p[i]=p[i-1]*131,ha[i]=ha[i-1]*131+s[i];
	int l=1,r=n/k;
	while(l<=r){
		long long mid=(l+r)/2;
		if(check(mid))l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<ans;
}