【BZOJ1031】字符加密
字符串延长一倍后算出它的后缀数组，然后选择sa[i]<=n的加入答案。
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 | #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=100010;int sa[maxn<<1];char s[maxn<<1],ans[maxn];int n,ansn;int c[maxn<<1],t1[maxn<<1],t2[maxn<<1];void Build_SA(){ int i,m=255,*x=t1,*y=t2; for (i=0;i<=m;i++) c[i]=0; for (i=1;i<=n;i++) c[x[i]=s[i]]++; for (i=1;i<=m;i++) c[i]+=c[i-1]; for (i=n;i;i--) sa[c[x[i]]--]=i; for (int k=1;k<=n;k<<=1) { int p=0; for (i=n-k+1;i<=n;i++) y[++p]=i; for (i=1;i<=n;i++) if (sa[i]>k) y[++p]=sa[i]-k; for (i=0;i<=m;i++) c[i]=0; for (i=1;i<=n;i++) c[x[y[i]]]++; for (i=1;i<=m;i++) c[i]+=c[i-1]; for (i=n;i;i--) sa[c[x[y[i]]]--]=y[i]; swap(x,y);p=1;x[sa[1]]=1; for (i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?p:++p; if (p>=n) break; m=p; }}int main(){ scanf("%s",s+1); n=strlen(s+1); for (int i=n+1;i<=(n<<1);i++) s[i]=s[i-n]; n<<=1; Build_SA(); for (int i=1;i<=n;i++) if (sa[i]<=(n>>1)) ans[++ansn]=s[sa[i]+(n>>1)-1]; printf("%s\n",ans+1); return 0;} |
评论 (0)
