[BZOJ] [P2946] [Poi 2000] [공공 꼬치] [문제 풀이] [hash]
1381 단어 bzoj
hash + 2 점 물 문제 안 할 게 요.
사실 주로 나의 새 노트 를 테스트 하 는 데 쓰 인 다. 정말 시원 하 다!!
슬 래 그 설정 을 붙 이지 않 는 게 좋 을 것 같 아 요. - |
Code:
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long UL;
int n,mn=2001,len[6];
UL base=233;
UL hash[6][2010],hash_l[2010];
char s[2010];
UL hshs(int i,int l,int r){
// cerr<<hash[i][r]-hash[i][l-1]*hash_l[r-l+1]<<endl;
return hash[i][r]-hash[i][l-1]*hash_l[r-l+1];
}
set<UL>S1,S2;
bool ok(int l){
S1.clear();S2.clear();
for(int i=1;i+l-1<=len[1];i++)S1.insert(hshs(1,i,i+l-1));
for(int i=2;i<=n;i++){
for(int j=1;j+l-1<=len[i];j++){
UL h=hshs(i,j,j+l-1);
if(S1.count(h))S2.insert(h);
}S1=S2;S2.clear();
}return S1.size();
}
int main(){
scanf("%d",&n);
hash_l[0]=1;
for(int i=1;i<=2000;i++)hash_l[i]=hash_l[i-1]*base;
for(int i=1;i<=n;i++){
scanf("%s",s+1);
UL val=0;len[i]=strlen(s+1);mn=min(mn,len[i]);
for(int j=1;j<=len[i];j++)
hash[i][j]=hash[i][j-1]*base+s[j]-'a';
}
int l=0,r=mn+1;
while(l<r){
int mid=(l+r)>>1;
if(ok(mid))
l=mid+1;
else r=mid;
}cout<<l-1<<endl;
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
