RT

ATCoder 本地WA 洛谷IDE AC

求捉虫

#include<map>
#include<cstdio>
#define int long long
#define mod 1000000007
#define base 131
int n,hash[5005];
char str[5005];
int pow(int a,int b)
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	int ans=pow(a,b/2);
	ans=ans*ans%mod;
	if(b&1)
		ans=ans*a%mod;
	return ans;
}
int check(int m)
{
	std::map <int,int> mp;
	int k=pow(base,m);
	for(int i=1;i<=n;i++)
	{
		if(i+m-1>n)
			break;
		int t=(hash[i+m-1]-hash[i-1]*k%mod+mod)%mod;
		if(mp.find(t)!=mp.end())
		{
			if(mp[t]+m-1<i)
				return 1;
		}
		else
			mp[t]=i;
	}
	return 0;
}
signed main()
{
	std::scanf("%lld %s",&n,str+1);
	for(int i=1;i<=n;i++)
	 	str[i]=str[i]-'a';
	for(int i=1;i<=n;i++)
		hash[i]=(hash[i-1]*base+str[i])%mod;
	int l=1,r=n,ans=0;
	while(l<=r)
	{
		int m=(l+r)/2;
		if(check(m))
			ans=m,l=m+1;
		else
			r=m-1;
	}
	std::printf("%lld",ans);
}