AcWing 1460. 我在哪?
原题链接
简单
作者:
bhb
,
2022-02-13 14:52:32
,
所有人可见
,
阅读 273
字符串哈希
#include<bits/stdc++.h>
using namespace std;
int P = 131;
typedef unsigned long long ULL;
const int N =110;
ULL p[N],h[N];
string s;
int n=0;
ULL get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
bool check(int k)
{
unordered_set<ULL>st;
for(int i=1;i+k-1<=n;i++)
{
auto c=get(i,i+k-1);
if(!st.count(c))
st.insert(c);
else
return false;
}
return true;
}
int main()
{
cin>>n;
cin>>s;
p[0]=1;
for(int i=1;i<=n;i++)
{
h[i]=h[i-1]*P+s[i-1];
p[i]=p[i-1]*P;
}
int l=1,r=n;
while(l<r)
{
int m=l+r>>1;
if(check(m))//从左向右找到最小值
r=m;
else
l=m+1;
}
cout<<l;
return 0;
}