|
|
back to boardWA#12 Posted by jerry 15 Jul 2017 07:25 tried 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 :) Re: WA#12 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. Re: WA#12 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 |
|
|