题解

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
const int mod1=998244353;
const int mod2=1e9+7;
const int base1=37;
const int base2=39;
inline char cread(){
int x=0;
char c=getchar();
for(;!(c>='a'&&c<='z');c=getchar());
return c;
}
pair<int,int>Tmp[maxn];
int a[maxn];
int n,H1[maxn],H2[maxn],Pow1[maxn],Pow2[maxn];
int Hash1(int l,int r){
return ((H1[r]-H1[l-1]1llPow1[r-l+1])%mod1+mod1)%mod1;
}
int Hash2(int l,int r){
return ((H2[r]-H2[l-1]1llPow2[r-l+1])%mod2+mod2)%mod2;
}
bool check(int x){
for(int i=x;i<=n;i++)
Tmp[i-x+1]=make_pair(Hash1(i-x+1,i),Hash2(i-x+1,i));
sort(Tmp+1,Tmp+n-x+2);
for(int i=2;i<=n-x+1;i++)
if(Tmp[i-1]==Tmp[i]) return 1;
return 0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) a[i]=cread()-'a';
Pow1[0]=Pow2[0]=1;
for(int i=1;i<=n;i++){
H1[i]=(H1[i-1]1llbase1+a[i])%mod1;
H2[i]=(H2[i-1]1llbase2+a[i])%mod2;
Pow1[i]=(Pow1[i-1]1llbase1)%mod1;
Pow2[i]=(Pow2[i-1]1llbase2)%mod2;
}
int l=0,r=n-1,mid;
while(r>l){
mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
return 0;
}