社区讨论
help,玄关
P6456[COCI 2006/2007 #5] DVAPUT参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mlwd1iq1
- 此快照首次捕获于
- 2026/02/21 21:34 2 周前
- 此快照最后确认于
- 2026/02/22 11:28 2 周前
WA10
CPP#include<iostream>
#include<unordered_map>
using namespace std;
int ha[200005],pw[200005],ha1[200005],pw1[200005];
unordered_map<int,bool> f;
const int mod1=1e9+7,mod2=1e9+9;
int n;
string x;
int h(int l,int r){
return (ha[r]-(1ll*ha[l-1]*pw[r-l+1])%mod1+mod1)%mod1;
}
int h2(int l,int r){
return (ha1[r]-(1ll*ha1[l-1]*pw1[r-l+1])%mod2+mod2)%mod2;
}
bool check(int x){
f.clear();
for(int i=x;i<=n;i++){
if(f[h(i-x+1,i)]==1)return 1;
f[h(i-x+1,i)]=1;
}
return 0;
}
signed main(){
cin>>n;
cin>>x;
x=" "+x;
pw[0]=1;
for(int i=1;i<=n;i++){
ha[i]=(1ll*ha[i-1]*13331+x[i])%mod1;
ha1[i]=(1ll*ha1[i-1]*13331+x[i])%mod2;
pw[i]=(1ll*pw[i-1]*13331)%mod1;
pw1[i]=(1ll*pw1[i-1]*13331)%mod2;
}
int l=-1,r=n;
while(r-l>1){
int mid=(l+r)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<r;
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...