一道很简单的后缀数组题
把字符串重复两次求个后缀数组,然后依次把开头在第一遍字符串中的字符串对应的最后末尾输出。
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 |
// <1031.cpp> - 05/14/16 22:00:59 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=200010; const int INF=1e9; int n,L; char s[MAXN]; int sa[MAXN],rk[MAXN]; int v[MAXN],x[MAXN],y[MAXN]; void go(){ int m=300; for(int i=1;i<=n;i++)v[x[i]=s[i]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[i]]--]=i; for(int j=1;j<=n;j<<=1){ int p=0; for(int i=n-j+1;i<=n;i++)y[++p]=i; for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j; for(int i=1;i<=m;i++)v[i]=0; for(int i=1;i<=n;i++)v[x[y[i]]]++; for(int i=2;i<=m;i++)v[i]+=v[i-1]; for(int i=n;i;i--)sa[v[x[y[i]]]--]=y[i]; swap(x,y);x[sa[1]]=1; p=1; for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p; if(p==n)break;m=p; } } int main(){ scanf("%s",s+1); L=strlen(s+1); for(int i=1;i<=L;i++)s[L+i]=s[i]; n=L<<1; go(); for(int i=1;i<=n;i++)if(sa[i]<=L)putchar(s[sa[i]+L-1]); return 0; } |