哈希表
枚举子串长度 k
把每个子串的哈希值加到哈希表里
用哈希表判重
因为子串可以反转
所以要两个哈希
一个从前往后，一个从后往前
复杂度为O(n + n/2 + n/3+ ... + n/n) 约等于 O(n ln n)
但是每次长度k更新都要清空哈希表
非常耗时（只有60分）
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; typedef unsigned long long ull; const int mo=1e6+7;//模数 const long long base=1e9+7;//这里base要大一些，不然容易冲突 int n,a[mo+10],mx,ans[mo+10],tot; ull h1[mo+10],h2[mo+10],fac[mo+10],hset[mo+10];//前缀哈希，后缀哈希以及哈希表 int from[mo+10],fir[mo+10],cnt;//哈希表的实现用链式前向星 inline void add(ull hs)//添加一个值到哈希表里 { int t=hs%mo; from[++cnt]=fir[t]; fir[t]=cnt; hset[cnt]=hs; } inline bool find(ull hs)//判断重复 { int t=hs%mo; for(int i=fir[t];i;i=from[i]) if(hset[i]==hs) return 1; return 0; } int main() { cin>>n; fac[0]=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); fac[i]=fac[i-1]*base; h1[i]=h1[i-1]*base+a[i]; } for(int i=n;i;i--) h2[i]=h2[i+1]*base+a[i]; //预处理前缀后缀哈希值 for(int i=1;i<=n;i++) { cnt=0; memset(from,0,sizeof(from)); memset(fir,0,sizeof(fir)); memset(hset,0,sizeof(hset)); //每次清空哈希表 int s=0; for(int j=i;j<=n;j+=i) { ull hs1=h1[j]-h1[j-i]*fac[i];//取出子串哈希值 if(find(hs1)) continue;//判重 ull hs2=h2[j-i+1]-h2[j+1]*fac[i];//取出子串反转后的哈希值 if(find(hs2)) continue;//判重 add(hs1); add(hs2);//把两个哈希值都加到哈希表里 s++; } if(s>mx) mx=s,ans[tot=1]=i; else if(s==mx) ans[++tot]=i; //尝试更新答案 } cout<<mx<<" "<<tot<<endl; for(int i=1;i<=tot;i++) printf("%d ",ans[i]); return 0; }
所以考虑增加一个时间戳tim
记录当前哈希值是什么时候加入的
就不用清空了
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; typedef unsigned long long ull; const int mo=1e7+7;//模数 const long long base=1e9+7;//这里base要大一些，不然容易冲突 int n,a[mo+10],mx,ans[mo+10],tot; ull h1[mo+10],h2[mo+10],fac[mo+10],hset[mo+10];//前缀哈希，后缀哈希以及哈希表 int from[mo+10],fir[mo+10],cnt,tim[mo+10];//哈希表的实现用链式前向星 inline void add(ull hs,int k)//添加一个值到哈希表里,k为时间 { int t=hs%mo; from[++cnt]=fir[t]; fir[t]=cnt; hset[cnt]=hs; tim[cnt]=k;//时间戳，记录当前哈希值是在什么时候加入的 } inline bool find(ull hs,int k)//判断重复 { int t=hs%mo; for(int i=fir[t];i;i=from[i]) if(hset[i]==hs&&tim[i]==k) return 1; return 0; } int main() { cin>>n; fac[0]=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); fac[i]=fac[i-1]*base; h1[i]=h1[i-1]*base+a[i]; } for(int i=n;i;i--) h2[i]=h2[i+1]*base+a[i]; //预处理前缀后缀哈希值 for(int i=1;i<=n;i++) { int s=0; for(int j=i;j<=n;j+=i) { ull hs1=h1[j]-h1[j-i]*fac[i];//取出子串哈希值 if(find(hs1,i)) continue;//判重 ull hs2=h2[j-i+1]-h2[j+1]*fac[i];//取出子串反转后的哈希值 if(find(hs2,i)) continue;//判重 add(hs1,i); add(hs2,i);//把两个哈希值都加到哈希表里 s++; } if(s>mx) mx=s,ans[tot=1]=i; else if(s==mx) ans[++tot]=i; //尝试更新答案 } cout<<mx<<" "<<tot<<endl; for(int i=1;i<=tot;i++) printf("%d ",ans[i]); return 0; }