|
|
back to boardtried all mentioned test cases .all correct. still WA on #12. using surfix array.any idea? code here: #include <cstdio> #include <cstring> int const N=220000; int st[256], rank[2*N], rank1[2*N], count[N], tmp[N]; char a[N], b[N], s[N], max1; int sa[N], height[N], si; int main(){ memset(st, 0, sizeof st); memset(rank, 0, sizeof rank); memset(rank1, 0, sizeof rank1); scanf("%s", b); int n1=strlen(b); for(int i=1; i<=n1; ++i)a[i]=b[i-1]; for(int i=1; i<=n1; ++i)a[i+n1+1]=b[n1-i]; a[0]=' '; a[n1+1]='#'; int n=2*n1+1; a[n+1]='&'; for(int i=1; i<=n; ++i)st[a[i]]=1; for(int i=1; i<=255; ++i)st[i]+=st[i-1]; for(int i=1; i<=n; ++i)rank[i]=st[a[i]];
int k=0; for(int p=1; k!=n; p+=p){ memset(count, 0, sizeof count); for(int i=1; i<=n; ++i)count[rank[i+p]]++; for(int i=1; i<=n; ++i)count[i]+=count[i-1]; for(int i=n; i>=1; --i)tmp[count[rank[i+p]]--]=i;
memset(count, 0, sizeof count); for(int i=1; i<=n; ++i)count[rank[i]]++; for(int i=1; i<=n; ++i)count[i]+=count[i-1]; for(int i=n; i>=1; --i)sa[count[rank[tmp[i]]]--]=tmp[i];
memcpy(rank1, rank, sizeof rank1); rank[sa[1]]=k=1; for(int i=2; i<=n; ++i){ if(rank1[sa[i]]!=rank1[sa[i-1]] or rank1[sa[i]+p]!=rank1[sa[i-1]+p])++k; rank[sa[i]]=k; } } k=0; for(int i=1; i<=n; ++i){ if(rank[i]==1){ k=0; }else{ --k; if(k<0)k=0; while(a[i+k]==a[sa[rank[i]-1]+k])++k; } height[rank[i]]=k; }
int max=-1; for(int i=2; i<=n; ++i){ int p=sa[i]; int q=sa[i-1]; if((p-1)/n1 != (q-1)/n1){ if(p+q+height[i]==n+2){ if(height[i]>max){ max=height[i]; si=p; } } } } for(int i=si; i<si+max; ++i)printf("%c", a[i]); return 0; } THX :) Are interesting in solving the task or in solving the task with suffix array or in knowing why your program outputs wrong at #12? Probably third is the case... So I tried to read your program. Have not understand. Maybe you elaborate details of your algorithm. You need to output the first of them if there are several such strings.But when you correct it ,i guess you 'll WA #18 |
|
|