【算法】后缀数组
【题解】把数组复制一遍然后SA处理即可。
#include#include #include using namespace std;const int maxn=300010;int sa[maxn],base[maxn],y[maxn],x[maxn],n;char s[maxn];void build_sa(int m){ //初始基排-4步 for(int i=1;i<=m;i++)base[i]=0;//初始化 for(int i=1;i<=n;i++)base[x[i]=s[i]+1]++;//累积 for(int i=2;i<=m;i++)base[i]+=base[i-1];//叠加排名 for(int i=n;i>=1;i--)sa[base[x[i]]--]=i;//排名赋值(愈前愈前，但无所谓) for(int k=1;k<=n;k<<=1)//倍增 { int p=0; //排序第二关键字 for(int i=n-k+1;i<=n;i++)y[++p]=i;//没有第二关键字默认为$ for(int i=1;i<=n;i++)if(sa[i]>k)y[++p]=sa[i]-k;//根据sa决定第二关键字排名，注意k即以后才能作为第二关键字 sa[i]-k取对应第一关键字(后缀) //排序第一关键字 for(int i=1;i<=m;i++)base[i]=0; for(int i=1;i<=n;i++)base[x[i]]++; for(int i=2;i<=m;i++)base[i]+=base[i-1]; for(int i=n;i>=1;i--)sa[base[x[y[i]]]--]=y[i];//根据y顺序(倒)赋值SA //把x放进y，然后更新x swap(x,y); p=1;x[sa[1]]=1; for(int i=2;i<=n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p:++p;//判重 if(p>=n)break;//排名各不相同即退出 m=p; }}int main(){ scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++)s[n+i]=s[i]; n*=2; build_sa(256); for(int i=1;i<=n;i++)if(sa[i]<=n/2)printf("%c",s[sa[i]+n/2-1]); return 0;}