二分答案，然后搞出hash值扔到哈希表里。期望復雜度O(n*log(n))。

<法一>next數組版哈希表

#include<cstdio> #include<cstring> using namespace std; typedef unsigned long long ull; const ull seed=29; #define MOD 2007 ull seeds[2001],ord[301],v[6][2000]; int n,ls[6],minv=2147483647,mini,first[6][MOD],next[6][2000],en[6]; char s[6][2001]; void AddEdge(const int &o,const int &U,const ull &V) {v[o][en[o]]=V;next[o][en[o]]=first[o][U];first[o][U]=en[o]++; } 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(const int &o,const ull &x) {int y=(int)(x%MOD);for(int i=first[o][y];i!=-1;i=next[o][i]) if(v[o][i]==x) return 1;return 0; } bool Find_In_All(const ull &x) {for(int i=1;i<=n;++i)if(i!=mini&&(!Find(i,x)))return 0;return 1; } bool check(const int &x) {memset(first,-1,sizeof(first));memset(en,0,sizeof(en));for(int i=1;i<=n;++i) if(i!=mini){ull hs=BKDRhash(s[i],0,x);AddEdge(i,hs%MOD,hs);for(int j=x;j<ls[i];++j){hs=hs*seed+ord[s[i][j]];hs-=seeds[x]*ord[s[i][j-x]];AddEdge(i,hs%MOD,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 l=0,r=minv+1;while(l<r){ int mid=l+r>>1; if(check(mid)) l=mid+1; else r=mid;}printf("%d\n",l-1);return 0; }

<法二>vector版哈希表

#include<cstdio> #include<cstring> #include<vector> using namespace std; typedef unsigned long long ull; const ull seed=29; #define MOD 2007 typedef vector<ull>::iterator VER; vector<ull>List[6][2007]; ull seeds[2001],ord[301]; int n,ls[6],minv=2147483647,mini; 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(const int &o,const ull &x) {int y=(int)(x%MOD);for(VER it=List[o][y].begin();it!=List[o][y].end();++it)if(*it==x)return 1;return 0; } bool Find_In_All(const ull &x) {for(int i=1;i<=n;++i)if(i!=mini&&(!Find(i,x)))return 0;return 1; } bool check(const int &x) {for(int i=1;i<=n;++i) if(i!=mini){ull hs=BKDRhash(s[i],0,x);List[i][hs%MOD].push_back(hs);for(int j=x;j<ls[i];++j){hs=hs*seed+ord[s[i][j]];hs-=seeds[x]*ord[s[i][j-x]];List[i][hs%MOD].push_back(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 l=0,r=minv+1;while(l<r){ int mid=l+r>>1; if(check(mid)) l=mid+1; else r=mid;}printf("%d\n",l-1);return 0; }

轉載于:https://www.cnblogs.com/autsky-jadek/p/4245097.html

總結

以上是生活随笔為你收集整理的【二分答案】【哈希表】【字符串哈希】bzoj2946 [Poi2000]公共串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。