首页 > 代码库 > 【二分答案】【分块答案】【字符串哈希】【set】bzoj2946 [Poi2000]公共串
【二分答案】【分块答案】【字符串哈希】【set】bzoj2946 [Poi2000]公共串
我们二分/分块枚举答案x，暴力把除了最短的字符串以外的其他字符串的x长度子串哈希搞出来，分别扔到set里。
然后暴力枚举最短的字符串的x长度字串，查看是否在全部的set里出现过。
#include<cstdio>#include<set>#include<cstring>#include<cmath>using namespace std;typedef unsigned long long ull;set<ull>T[6];const ull seed=29;ull seeds[2001],ord[301];int n,ls[6],minv=2147483647,mini,ans;char s[6][2001];ull BKDRhash(const char str[],const int &L,const int &R){ ull res=0; for(int i=L;i<R;++i) res=res*seed+ord[str[i]]; return res;}void init(){ for(int i=‘a‘,j=1;i<=‘z‘;++i,++j) ord[i]=(ull)j; seeds[0]=1; for(int i=1;i<=minv;++i) seeds[i]=seeds[i-1]*seed;}bool Find_In_All(const ull &x){ for(int i=1;i<=n;++i) if(i!=mini) if(T[i].find(x)==T[i].end()) return 0; return 1;}bool check(const int &x){ for(int i=1;i<=n;++i) if(i!=mini) { T[i].clear(); ull hs=BKDRhash(s[i],0,x); T[i].insert(hs); for(int j=x;j<ls[i];++j) { hs=hs*seed+ord[s[i][j]]; hs-=seeds[x]*ord[s[i][j-x]]; T[i].insert(hs); } } ull hs=BKDRhash(s[mini],0,x); if(Find_In_All(hs)) return 1; for(int i=x;i<minv;++i) { hs=hs*seed+ord[s[mini][i]]; hs-=seeds[x]*ord[s[mini][i-x]]; if(Find_In_All(hs)) return 1; } return 0;}int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%s",s[i]); ls[i]=strlen(s[i]); if(ls[i]<minv) { minv=ls[i]; mini=i; } } init(); int sz=sqrt(minv),last=minv+1; for(int i=minv;last;i-=sz) { if(check(i)) for(int j=last-1;j>=i;--j) if(check(j)) { printf("%d\n",j); return 0; } last=i; }}【二分答案】【分块答案】【字符串哈希】【set】bzoj2946 [Poi2000]公共串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。