@OceanEye8年前
08/14
15:59
嗯这题不是权限题 很友好
SA裸题
把原串复制一遍接在最后面，跑一遍SA
只需要把SA中在[1,len]范围内的放入答案数组就好了
写得比较直接……就比较丑，各位见谅
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 200010 char s[N],ans[N]; int SA[N],rk[N]; int set[N],a[N],fir[N],sec[N],buc[N],tmp[N],n; void make_SA() { copy(s+1,s+1+n,set+1); sort(set+1,set+1+n); For(i,1,n) a[i]=lower_bound(set+1,set+1+n,s[i])-set; fill(buc,buc+1+n,0); For(i,1,n) buc[a[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) rk[i]=buc[a[i]-1]+1; bool unique; for(int p=1;p<=n;p<<=1) { For(i,1,n) fir[i]=rk[i],sec[i]=(i+p)>n?0:rk[i+p]; fill(buc,buc+1+n,0); For(i,1,n) buc[sec[i]]++; For(i,1,n) buc[i]+=buc[i-1]; For(i,1,n) tmp[n- --buc[sec[i]]]=i; fill(buc,buc+1+n,0); For(i,1,n) buc[fir[i]]++; For(i,1,n) buc[i]+=buc[i-1]; for(int j=1,i;j<=n;j++) { i=tmp[j]; SA[buc[fir[i]]--]=i; } unique=true; for(int j=1,i,last=0;j<=n;j++) { i=SA[j]; if(!last) rk[i]=1; else if(fir[last]==fir[i]&&sec[last]==sec[i]) rk[i]=rk[last],unique=false; else rk[i]=rk[last]+1; last=i; } if(unique) break; } } void init() { scanf("%s",s+1); n=strlen(s+1); copy(s+1,s+1+n,s+1+n); n<<=1; // printf("%s %d\n",s+1,n); } int main() { init(); make_SA(); int m=n>>1,last=0; For(i,1,n) { // printf("%d\n",SA[i]); if(SA[i]<=m) ans[last++]=s[SA[i]+m-1]; } printf("%s",ans); return 0; } |