记录编号 | 218929 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [SPOJ 687] 重复的字符串 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 8.659 s | ||
提交时间 | 2016-01-12 11:07:06 | 内存使用 | 7.01 MiB | ||
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> using namespace std; const int SIZEN=60010,SIZEG=20; int T,N; char p[SIZEN]; int t[SIZEN]={0},rank[SIZEN],sa[SIZEN],height[SIZEN]; int A[SIZEN],B[SIZEN]; int x[SIZEN],y[SIZEN]; int sum[SIZEN]; int ST[SIZEN][SIZEG]; void basesort(int a[],int b[],int c[],int n,int m) { for(int i=0;i<=m;i++) sum[i]=0; for(int i=0;i<n;i++) sum[b[a[i]]]++; for(int i=1;i<=m;i++) sum[i]+=sum[i-1]; for(int i=n-1;i>=0;i--) c[--sum[b[a[i]]]]=a[i]; } void sort_suf(int t[],int rank[],int sa[],int n) { for(int i=0;i<n;i++) A[i]=i,x[i]=t[i]; basesort(A,x,sa,n,2); rank[sa[0]]=1; for(int i=1;i<n;i++) if(x[sa[i]]==x[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]]; else rank[sa[i]]=rank[sa[i-1]]+1; for(int k=1;k<=n;k<<=1) { for(int i=0;i<n;i++) { A[i]=i; x[i]=rank[i]; if(i+k<n) y[i]=rank[i+k]; else y[i]=0; } basesort(A,y,B,n,n); basesort(B,x,sa,n,n); //for(int i=0;i<n;i++) cout<<i<<" "<<sa[i]<<endl; //cout<<endl; rank[sa[0]]=1; for(int i=1;i<n;i++) if(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]]; else rank[sa[i]]=rank[sa[i-1]]+1; //for(int i=0;i<n;i++) cout<<i<<" "<<rank[i]<<endl; //cout<<endl; } } void make_height() { int h=0; for(int i=0;i<N;i++) { if(rank[i]==1) h=0; else { int k=sa[rank[i]-2]; if(--h<0) h=0; while(t[i+h]==t[k+h]) h++; } height[rank[i]]=h; } } void make_ST() { int n=int(log2(N+1.0)); for(int i=0;i<=N;i++) ST[i][0]=height[i]; for(int j=1;j<=n;j++) { for(int i=0;i<=N;i++) { //cout<<i<<endl;//" "<<" "<<i+(1<<(j-1))<<" "<<j<<endl; ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]); } } } void read() { scanf("%d",&N); memset(t,0,sizeof(t)); memset(ST,0,sizeof(ST)); memset(height,0,sizeof(height)); for(int i=0;i<N;i++) { cin>>p[i]; if(p[i]=='a') t[i]=1; else t[i]=2; } } int RMQ(int x,int y) { int p=int(log2(y-x+1)); int re=min(ST[x][p],ST[y-(1<<p)+1][p]); return re; } int lcp(int x,int y) { if(x==y) return N-x; int a=rank[x],b=rank[y]; if(a>b) swap(a,b); return RMQ(a+1,b); } int ans; void test(int x) { for(int i=0;i<N;i+=x) { int tem=lcp(i,i+x); int st=i-(x-tem%x); int pos=tem/x+1; if(st>0&&tem%x!=0) { if(lcp(st,st+x)>tem) pos++; } ans=max(ans,pos); } } void work() { ans=0; for(int i=1;i<=N;i++) test(i); printf("%d\n",ans); } void prepare() { sort_suf(t,rank,sa,N); make_height(); make_ST(); } int main() { freopen("repeats.in","r",stdin); freopen("repeats.out","w",stdout); scanf("%d",&T); int now=1; while(now<=T) { read(); prepare(); work(); now++; } return 0; }